
<!DOCTYPE HTML>
<html lang="zh-hans" >
    <head>
        <meta charset="UTF-8">
        <meta content="text/html; charset=utf-8" http-equiv="Content-Type">
        <title>3.广度优先搜索算法 · 计算机 ,java , 大数据 基础知识体系</title>
        <meta http-equiv="X-UA-Compatible" content="IE=edge" />
        <meta name="description" content="">
        <meta name="generator" content="GitBook 3.2.3">
        <meta name="author" content="hzh">
        
        
    
    <link rel="stylesheet" href="../gitbook/style.css">

    
            
                
                <link rel="stylesheet" href="../gitbook/gitbook-plugin-splitter/splitter.css">
                
            
                
                <link rel="stylesheet" href="../gitbook/gitbook-plugin-expandable-chapters-small/expandable-chapters-small.css">
                
            
                
                <link rel="stylesheet" href="../gitbook/gitbook-plugin-anchors/plugin.css">
                
            
                
                <link rel="stylesheet" href="../gitbook/gitbook-plugin-anchor-navigation-ex/style/plugin.css">
                
            
                
                <link rel="stylesheet" href="../gitbook/gitbook-plugin-expandable-chapters/expandable-chapters.css">
                
            
                
                <link rel="stylesheet" href="../gitbook/gitbook-plugin-toggle-chapters/toggle.css">
                
            
                
                <link rel="stylesheet" href="../gitbook/gitbook-plugin-back-to-top-button/plugin.css">
                
            
                
                <link rel="stylesheet" href="../gitbook/gitbook-plugin-code/plugin.css">
                
            
                
                <link rel="stylesheet" href="../gitbook/gitbook-plugin-search-pro/search.css">
                
            
                
                <link rel="stylesheet" href="../gitbook/gitbook-plugin-pageview-count/plugin.css">
                
            
                
                <link rel="stylesheet" href="../gitbook/gitbook-plugin-highlight/website.css">
                
            
                
                <link rel="stylesheet" href="../gitbook/gitbook-plugin-fontsettings/website.css">
                
            
        

    

    
        
    

        
    
    
    
    <meta name="HandheldFriendly" content="true"/>
    <meta name="viewport" content="width=device-width, initial-scale=1, user-scalable=no">
    <meta name="apple-mobile-web-app-capable" content="yes">
    <meta name="apple-mobile-web-app-status-bar-style" content="black">
    <link rel="apple-touch-icon-precomposed" sizes="152x152" href="../gitbook/images/apple-touch-icon-precomposed-152.png">
    <link rel="shortcut icon" href="../gitbook/images/favicon.ico" type="image/x-icon">

    
    <link rel="next" href="../jvm/1.jvm内存结构.html" />
    
    
    <link rel="prev" href="2.深度优先搜索题目集.html" />
    

    
    
    
    

    </head>
    <body>
        
<div class="book">
    <div class="book-summary">
        
            
<div id="book-search-input" role="search">
    <input type="text" placeholder="输入并搜索" />
</div>

            
                <nav role="navigation">
                


<ul class="summary">
    
    

    

    
        
        <li class="header">操作系统</li>
        
        
    
        <li class="chapter " data-level="1.1" data-path="../">
            
                <a href="../">
            
                    
                    Introduction
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="1.2" data-path="../操作系统/1.基本概述.html">
            
                <a href="../操作系统/1.基本概述.html">
            
                    
                    1.操作系统基本概述
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="1.3" data-path="../操作系统/2.进程管理之进程与线程.html">
            
                <a href="../操作系统/2.进程管理之进程与线程.html">
            
                    
                    2.进程管理之进程与线程
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="1.4" data-path="../操作系统/3.进程管理之处理机调度.html">
            
                <a href="../操作系统/3.进程管理之处理机调度.html">
            
                    
                    3.进程管理之处理机调度
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="1.5" data-path="../操作系统/4.进程管理之进程同步.html">
            
                <a href="../操作系统/4.进程管理之进程同步.html">
            
                    
                    4.进程管理之进程同步
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="1.6" data-path="../操作系统/5.内存管理之基本概念.html">
            
                <a href="../操作系统/5.内存管理之基本概念.html">
            
                    
                    5.内存管理之基本概念
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="1.7" data-path="../操作系统/6.内存管理之虚拟内存.html">
            
                <a href="../操作系统/6.内存管理之虚拟内存.html">
            
                    
                    6.内存管理之虚拟内存
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="1.8" data-path="../操作系统/7.IO设备管理之基本概念.html">
            
                <a href="../操作系统/7.IO设备管理之基本概念.html">
            
                    
                    7.IO设备管理之基本概念
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="1.9" data-path="../操作系统/8.面试题总结一.html">
            
                <a href="../操作系统/8.面试题总结一.html">
            
                    
                    8.面试题总结一
            
                </a>
            

            
        </li>
    

    
        
        <li class="header">计算机网络篇</li>
        
        
    
        <li class="chapter " data-level="2.1" data-path="../计算机网络/1.计算机网络入门基础概念.html">
            
                <a href="../计算机网络/1.计算机网络入门基础概念.html">
            
                    
                    1.计算机网络入门文章(必读)
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="2.2" data-path="../计算机网络/2.计算机网络通信基础.html">
            
                <a href="../计算机网络/2.计算机网络通信基础.html">
            
                    
                    2.计算机网络通信入门文章(必读)
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="2.3" data-path="../计算机网络/3.数据链路层.html">
            
                <a href="../计算机网络/3.数据链路层.html">
            
                    
                    3.数据链路层
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="2.4" data-path="../计算机网络/4.网络层1.html">
            
                <a href="../计算机网络/4.网络层1.html">
            
                    
                    4.网络层(一)
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="2.5" data-path="../计算机网络/5.网络层2.html">
            
                <a href="../计算机网络/5.网络层2.html">
            
                    
                    5.网络层(二)
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="2.6" data-path="../计算机网络/6.传输层.html">
            
                <a href="../计算机网络/6.传输层.html">
            
                    
                    6.传输层
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="2.7" data-path="../计算机网络/7.应用层.html">
            
                <a href="../计算机网络/7.应用层.html">
            
                    
                    7.应用层(⭐)
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="2.8" data-path="../计算机网络/10.HTTP相关协议.html">
            
                <a href="../计算机网络/10.HTTP相关协议.html">
            
                    
                    8.HTTP相关及发展
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="2.9" >
            
                <span>
            
                    
                    9.websocket
            
                </span>
            

            
        </li>
    
        <li class="chapter " data-level="2.10" data-path="../计算机网络/9.面试题二.html">
            
                <a href="../计算机网络/9.面试题二.html">
            
                    
                    面试题总结一
            
                </a>
            

            
        </li>
    

    
        
        <li class="header">数据结构篇</li>
        
        
    
        <li class="chapter " data-level="3.1" data-path="../数据结构/1.图论.html">
            
                <a href="../数据结构/1.图论.html">
            
                    
                    1.图论
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="3.2" data-path="../数据结构/2.图论例题.html">
            
                <a href="../数据结构/2.图论例题.html">
            
                    
                    2.图论例题
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="3.3" data-path="../数据结构/3.散列表.html">
            
                <a href="../数据结构/3.散列表.html">
            
                    
                    3.散列表
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="3.4" data-path="../数据结构/4.排序算法.html">
            
                <a href="../数据结构/4.排序算法.html">
            
                    
                    4.排序算法
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="3.5" data-path="../数据结构/5.排序列题.html">
            
                <a href="../数据结构/5.排序列题.html">
            
                    
                    5.排序算法例题
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="3.6" data-path="../数据结构/6.树论.html">
            
                <a href="../数据结构/6.树论.html">
            
                    
                    6.树论
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="3.7" data-path="../数据结构/7.树论例题.html">
            
                <a href="../数据结构/7.树论例题.html">
            
                    
                    7.树论例题.md
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="3.8" data-path="../数据结构/9.模板.html">
            
                <a href="../数据结构/9.模板.html">
            
                    
                    数据结构模板
            
                </a>
            

            
        </li>
    

    
        
        <li class="header">算法篇</li>
        
        
    
        <li class="chapter " data-level="4.1" data-path="leetCode周赛题解.html">
            
                <a href="leetCode周赛题解.html">
            
                    
                    leetCode周赛记录
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="4.2" data-path="1.时间复杂度.html">
            
                <a href="1.时间复杂度.html">
            
                    
                    1.时间复杂度
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="4.3" data-path="2.深度优先搜索.html">
            
                <a href="2.深度优先搜索.html">
            
                    
                    2.深度优先搜索算法
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="4.4" data-path="2.深度优先搜索题目集.html">
            
                <a href="2.深度优先搜索题目集.html">
            
                    
                    2.深搜题目集
            
                </a>
            

            
        </li>
    
        <li class="chapter active" data-level="4.5" data-path="3.广度优先搜索.html">
            
                <a href="3.广度优先搜索.html">
            
                    
                    3.广度优先搜索算法
            
                </a>
            

            
        </li>
    

    
        
        <li class="header">JVM篇</li>
        
        
    
        <li class="chapter " data-level="5.1" data-path="../jvm/1.jvm内存结构.html">
            
                <a href="../jvm/1.jvm内存结构.html">
            
                    
                    1.jvm内存结构
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="5.2" data-path="../jvm/2.HotSpot虚拟机对象探秘.html">
            
                <a href="../jvm/2.HotSpot虚拟机对象探秘.html">
            
                    
                    2.HotSpot虚拟机对象探秘.md
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="5.3" data-path="../jvm/3.对象存亡与垃圾收集算法.html">
            
                <a href="../jvm/3.对象存亡与垃圾收集算法.html">
            
                    
                    3.对象存亡与垃圾收集算法.md
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="5.4" data-path="../jvm/4.HotSpot的算法细节与垃圾收集器.html">
            
                <a href="../jvm/4.HotSpot的算法细节与垃圾收集器.html">
            
                    
                    4.HotSpot的算法细节与垃圾收集器.md
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="5.5" data-path="../jvm/5.内存分配与回收策略.html">
            
                <a href="../jvm/5.内存分配与回收策略.html">
            
                    
                    5.内存分配与回收策略.md
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="5.6" data-path="../jvm/6.类文件结构.html">
            
                <a href="../jvm/6.类文件结构.html">
            
                    
                    6.类文件结构.md
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="5.7" data-path="../jvm/7.类加载机制.html">
            
                <a href="../jvm/7.类加载机制.html">
            
                    
                    7.类加载机制.md
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="5.8" data-path="../jvm/8.jvm逃逸分析.html">
            
                <a href="../jvm/8.jvm逃逸分析.html">
            
                    
                    8.逃逸分析技术
            
                </a>
            

            
        </li>
    

    
        
        <li class="header">多线程篇</li>
        
        
    
        <li class="chapter " data-level="6.1" data-path="../多线程/basic/0.多线程路线图.html">
            
                <a href="../多线程/basic/0.多线程路线图.html">
            
                    
                    1.多线程学习路线图
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="6.2" data-path="../多线程/basic/0.java内存模型与线程.html">
            
                <a href="../多线程/basic/0.java内存模型与线程.html">
            
                    
                    2.java内存模型与线程
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="6.3" data-path="../多线程/3.并行程序基础.html">
            
                <a href="../多线程/3.并行程序基础.html">
            
                    
                    2.并行程序基础
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="6.4" data-path="../多线程/basic/0.jhappenBefore与jvm指令重排.html">
            
                <a href="../多线程/basic/0.jhappenBefore与jvm指令重排.html">
            
                    
                    3.happenBefore与jvm指令重排序
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="6.5" data-path="../多线程/basic/1.synchronized与volatile.html">
            
                <a href="../多线程/basic/1.synchronized与volatile.html">
            
                    
                    4.synchronized与volatile.md
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="6.6" data-path="../多线程/basic/2.ThreadLocal.html">
            
                <a href="../多线程/basic/2.ThreadLocal.html">
            
                    
                    5.ThreadLocal.md
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="6.7" data-path="../多线程/cas/1.乐观锁与悲观锁.html">
            
                <a href="../多线程/cas/1.乐观锁与悲观锁.html">
            
                    
                    6.乐观锁与悲观锁.md
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="6.8" data-path="../多线程/cas/2.CAS与atomic类.html">
            
                <a href="../多线程/cas/2.CAS与atomic类.html">
            
                    
                    7.CAS与atomic类.md
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="6.9" data-path="../多线程/aqs/1.AQS.html">
            
                <a href="../多线程/aqs/1.AQS.html">
            
                    
                    8.AQS.md
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="6.10" data-path="../多线程/aqs/2.基于AQS的并发工具.html">
            
                <a href="../多线程/aqs/2.基于AQS的并发工具.html">
            
                    
                    9.基于AQS的并发工具.md
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="6.11" data-path="../多线程/blockingQueue/1.阻塞队列.html">
            
                <a href="../多线程/blockingQueue/1.阻塞队列.html">
            
                    
                    10.阻塞队列.md
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="6.12" data-path="../多线程/pond/1.线程池与底层原理.html">
            
                <a href="../多线程/pond/1.线程池与底层原理.html">
            
                    
                    11.线程池与底层原理.md
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="6.13" data-path="../多线程/10面试题一.html">
            
                <a href="../多线程/10面试题一.html">
            
                    
                    12.面试题一
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="6.14" data-path="../多线程/10面试题二.html">
            
                <a href="../多线程/10面试题二.html">
            
                    
                    13.面试题二.md
            
                </a>
            

            
        </li>
    

    
        
        <li class="header">java集合篇</li>
        
        
    
        <li class="chapter " data-level="7.1" data-path="../basic/collection/1.java集合.html">
            
                <a href="../basic/collection/1.java集合.html">
            
                    
                    1.集合架构
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="7.2" data-path="../basic/collection/2.HashMap源码分析.html">
            
                <a href="../basic/collection/2.HashMap源码分析.html">
            
                    
                    2.hashMap底层原理
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="7.3" data-path="../basic/collection/3.ConcurrentHashMap分析.html">
            
                <a href="../basic/collection/3.ConcurrentHashMap分析.html">
            
                    
                    3.ConcurrentHashMap分析
            
                </a>
            

            
        </li>
    

    
        
        <li class="header">设计模式篇</li>
        
        
    
        <li class="chapter " data-level="8.1" >
            
                <span>
            
                    
                    1.创造型模式
            
                </span>
            

            
        </li>
    
        <li class="chapter " data-level="8.2" data-path="../设计模式/factory/三种工厂模式介绍.html">
            
                <a href="../设计模式/factory/三种工厂模式介绍.html">
            
                    
                    三种工厂模式
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="8.3" data-path="../设计模式/factory/实战工厂模式.html">
            
                <a href="../设计模式/factory/实战工厂模式.html">
            
                    
                    实战工厂模式
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="8.4" data-path="../设计模式/factory/实战抽象工厂模式.html">
            
                <a href="../设计模式/factory/实战抽象工厂模式.html">
            
                    
                    实战抽象工厂模式
            
                </a>
            

            
        </li>
    

    
        
        <li class="header">mysql篇</li>
        
        
    
        <li class="chapter " data-level="9.1" data-path="../数据库/mysql/1.b树b+树的底层原理.html">
            
                <a href="../数据库/mysql/1.b树b+树的底层原理.html">
            
                    
                    1.mysql索引基础之b树与b+树⭐⭐
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="9.2" data-path="../数据库/mysql/2.mysql索引.html">
            
                <a href="../数据库/mysql/2.mysql索引.html">
            
                    
                    2.mysql索引及优化⭐⭐⭐⭐
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="9.3" data-path="../数据库/mysql/3.mysql存储引擎.html">
            
                <a href="../数据库/mysql/3.mysql存储引擎.html">
            
                    
                    3.mysql存储引擎.md
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="9.4" data-path="../数据库/mysql/4.多版本并发控制之mvcc原理.html">
            
                <a href="../数据库/mysql/4.多版本并发控制之mvcc原理.html">
            
                    
                    4.多版本并发控制之mvcc原理
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="9.5" data-path="../数据库/mysql/4.mysql事务.html">
            
                <a href="../数据库/mysql/4.mysql事务.html">
            
                    
                    5.mysql事务
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="9.6" data-path="../数据库/mysql/5.mysql锁机制.html">
            
                <a href="../数据库/mysql/5.mysql锁机制.html">
            
                    
                    6.mysql的锁机制
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="9.7" data-path="../数据库/mysql/6.mysql面试题一.html">
            
                <a href="../数据库/mysql/6.mysql面试题一.html">
            
                    
                    7.mysql面试题一
            
                </a>
            

            
        </li>
    

    
        
        <li class="header">高并发中间件篇</li>
        
        
    

    
        
        <li class="header">架构理论篇</li>
        
        
    
        <li class="chapter " data-level="11.1" data-path="../架构/0.架构演进.html">
            
                <a href="../架构/0.架构演进.html">
            
                    
                    1.架构演进
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="11.2" data-path="../架构/0.微服务架构与soa架构.html">
            
                <a href="../架构/0.微服务架构与soa架构.html">
            
                    
                    2.微服务架构与soa架构
            
                </a>
            

            
        </li>
    

    
        
        <li class="header">高可用系统篇</li>
        
        
    
        <li class="chapter " data-level="12.1" data-path="../高可用架构/1.限流.html">
            
                <a href="../高可用架构/1.限流.html">
            
                    
                    1.系统限流
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="12.2" data-path="../高可用系统/2.服务熔断.html">
            
                <a href="../高可用系统/2.服务熔断.html">
            
                    
                    2.服务熔断
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="12.3" data-path="../高可用系统/3.服务降级.html">
            
                <a href="../高可用系统/3.服务降级.html">
            
                    
                    3.服务降级
            
                </a>
            

            
        </li>
    

    
        
        <li class="header">spring-cloud 微服务篇</li>
        
        
    

    

    <li class="divider"></li>

    <li>
        <a href="https://www.gitbook.com" target="blank" class="gitbook-link">
            本书使用 GitBook 发布
        </a>
    </li>
</ul>


                </nav>
            
        
    </div>

    <div class="book-body">
        
            <div class="body-inner">
                
                    

<div class="book-header" role="navigation">
    

    <!-- Title -->
    <h1>
        <i class="fa fa-circle-o-notch fa-spin"></i>
        <a href=".." >3.广度优先搜索算法</a>
    </h1>
</div>




                    <div class="page-wrapper" tabindex="-1" role="main">
                        <div class="page-inner">
                            
<div id="book-search-results">
    <div class="search-noresults">
    
                                <section class="normal markdown-section">
                                
                                <div id="anchor-navigation-ex-navbar"><i class="fa fa-navicon"></i><ul><ul><li><span class="title-icon "></span><a href="#&#x4E00;-&#x7B97;&#x6CD5;&#x89E3;&#x91CA;"><b></b>&#x4E00; &#x7B97;&#x6CD5;&#x89E3;&#x91CA;</a></li><ul><li><span class="title-icon "></span><a href="#&#x4E00;&#x3001;&#x7B97;&#x6CD5;&#x6846;&#x67B6;"><b></b>&#x4E00;&#x3001;&#x7B97;&#x6CD5;&#x6846;&#x67B6;</a></li><li><span class="title-icon "></span><a href="#&#x4E8C;&#x3001;&#x4E8C;&#x53C9;&#x6811;&#x7684;&#x6700;&#x5C0F;&#x9AD8;&#x5EA6;"><b></b>&#x4E8C;&#x3001;&#x4E8C;&#x53C9;&#x6811;&#x7684;&#x6700;&#x5C0F;&#x9AD8;&#x5EA6;</a></li><li><span class="title-icon "></span><a href="#&#x4E09;&#x3001;&#x89E3;&#x5F00;&#x5BC6;&#x7801;&#x9501;&#x7684;&#x6700;&#x5C11;&#x6B21;&#x6570;"><b></b>&#x4E09;&#x3001;&#x89E3;&#x5F00;&#x5BC6;&#x7801;&#x9501;&#x7684;&#x6700;&#x5C11;&#x6B21;&#x6570;</a></li><li><span class="title-icon "></span><a href="#&#x56DB;&#x3001;&#x53CC;&#x5411;-bfs-&#x4F18;&#x5316;"><b></b>&#x56DB;&#x3001;&#x53CC;&#x5411; BFS &#x4F18;&#x5316;</a></li></ul><li><span class="title-icon "></span><a href="#&#x4E8C;-&#x5229;&#x7528;bfs&#x5DE7;&#x89E3;&#x76CA;&#x667A;&#x6E38;&#x620F;"><b></b>&#x4E8C; &#x5229;&#x7528;bfs&#x5DE7;&#x89E3;&#x76CA;&#x667A;&#x6E38;&#x620F;</a></li><ul><li><span class="title-icon "></span><a href="#&#x4E00;&#x3001;&#x9898;&#x76EE;&#x89E3;&#x6790;"><b></b>&#x4E00;&#x3001;&#x9898;&#x76EE;&#x89E3;&#x6790;</a></li><li><span class="title-icon "></span><a href="#&#x4E8C;&#x3001;&#x601D;&#x8DEF;&#x5206;&#x6790;"><b></b>&#x4E8C;&#x3001;&#x601D;&#x8DEF;&#x5206;&#x6790;</a></li></ul></ul></ul></div><a href="#" id="anchorNavigationExGoTop"><i class="fa fa-arrow-up"></i></a><h2 id="&#x4E00;-&#x7B97;&#x6CD5;&#x89E3;&#x91CA;"><a name="&#x4E00;-&#x7B97;&#x6CD5;&#x89E3;&#x91CA;" class="anchor-navigation-ex-anchor" href="#&#x4E00;-&#x7B97;&#x6CD5;&#x89E3;&#x91CA;"><i class="fa fa-link" aria-hidden="true"></i></a><a name="&#x4E00;-&#x7B97;&#x6CD5;&#x89E3;&#x91CA;" class="plugin-anchor" href="#&#x4E00;-&#x7B97;&#x6CD5;&#x89E3;&#x91CA;"><i class="fa fa-link" aria-hidden="true"></i></a>&#x4E00; &#x7B97;&#x6CD5;&#x89E3;&#x91CA;</h2>
<p>BFS &#x7684;&#x6838;&#x5FC3;&#x601D;&#x60F3;&#x5E94;&#x8BE5;&#x4E0D;&#x96BE;&#x7406;&#x89E3;&#x7684;&#xFF0C;&#x5C31;&#x662F;&#x628A;&#x4E00;&#x4E9B;&#x95EE;&#x9898;&#x62BD;&#x8C61;&#x6210;&#x56FE;&#xFF0C;&#x4ECE;&#x4E00;&#x4E2A;&#x70B9;&#x5F00;&#x59CB;&#xFF0C;&#x5411;&#x56DB;&#x5468;&#x5F00;&#x59CB;&#x6269;&#x6563;&#x3002;&#x4E00;&#x822C;&#x6765;&#x8BF4;&#xFF0C;&#x6211;&#x4EEC;&#x5199; BFS &#x7B97;&#x6CD5;&#x90FD;&#x662F;&#x7528;&#x300C;&#x961F;&#x5217;&#x300D;&#x8FD9;&#x79CD;&#x6570;&#x636E;&#x7ED3;&#x6784;&#xFF0C;&#x6BCF;&#x6B21;&#x5C06;&#x4E00;&#x4E2A;&#x8282;&#x70B9;&#x5468;&#x56F4;&#x7684;&#x6240;&#x6709;&#x8282;&#x70B9;&#x52A0;&#x5165;&#x961F;&#x5217;&#x3002;</p>
<p>BFS &#x76F8;&#x5BF9; DFS &#x7684;&#x6700;&#x4E3B;&#x8981;&#x7684;&#x533A;&#x522B;&#x662F;&#xFF1A;BFS &#x627E;&#x5230;&#x7684;&#x8DEF;&#x5F84;&#x4E00;&#x5B9A;&#x662F;&#x6700;&#x77ED;&#x7684;&#xFF0C;</p>
<p>&#x672C;&#x6587;&#x5C31;&#x7531;&#x6D45;&#x5165;&#x6DF1;&#x5199;&#x4E24;&#x9053; BFS &#x7684;&#x5178;&#x578B;&#x9898;&#x76EE;&#xFF0C;&#x5206;&#x522B;&#x662F;&#x300C;&#x4E8C;&#x53C9;&#x6811;&#x7684;&#x6700;&#x5C0F;&#x9AD8;&#x5EA6;&#x300D;&#x548C;&#x300C;&#x6253;&#x5F00;&#x5BC6;&#x7801;&#x9501;&#x7684;&#x6700;&#x5C11;&#x6B65;&#x6570;&#x300D;&#xFF0C;&#x624B;&#x628A;&#x624B;&#x6559;&#x4F60;&#x600E;&#x4E48;&#x5199; BFS &#x7B97;&#x6CD5;&#x3002;</p>
<h3 id="&#x4E00;&#x3001;&#x7B97;&#x6CD5;&#x6846;&#x67B6;"><a name="&#x4E00;&#x3001;&#x7B97;&#x6CD5;&#x6846;&#x67B6;" class="anchor-navigation-ex-anchor" href="#&#x4E00;&#x3001;&#x7B97;&#x6CD5;&#x6846;&#x67B6;"><i class="fa fa-link" aria-hidden="true"></i></a><a name="&#x4E00;&#x3001;&#x7B97;&#x6CD5;&#x6846;&#x67B6;" class="plugin-anchor" href="#&#x4E00;&#x3001;&#x7B97;&#x6CD5;&#x6846;&#x67B6;"><i class="fa fa-link" aria-hidden="true"></i></a>&#x4E00;&#x3001;&#x7B97;&#x6CD5;&#x6846;&#x67B6;</h3>
<p>&#x8981;&#x8BF4;&#x6846;&#x67B6;&#x7684;&#x8BDD;&#xFF0C;&#x6211;&#x4EEC;&#x5148;&#x4E3E;&#x4F8B;&#x4E00;&#x4E0B; BFS &#x51FA;&#x73B0;&#x7684;&#x5E38;&#x89C1;&#x573A;&#x666F;&#x597D;&#x5427;&#xFF0C;<strong>&#x95EE;&#x9898;&#x7684;&#x672C;&#x8D28;&#x5C31;&#x662F;&#x8BA9;&#x4F60;&#x5728;&#x4E00;&#x5E45;&#x300C;&#x56FE;&#x300D;&#x4E2D;&#x627E;&#x5230;&#x4ECE;&#x8D77;&#x70B9;<code>start</code>&#x5230;&#x7EC8;&#x70B9;<code>target</code>&#x7684;&#x6700;&#x8FD1;&#x8DDD;&#x79BB;&#xFF0C;&#x8FD9;&#x4E2A;&#x4F8B;&#x5B50;&#x542C;&#x8D77;&#x6765;&#x5F88;&#x67AF;&#x71E5;&#xFF0C;&#x4F46;&#x662F; BFS &#x7B97;&#x6CD5;&#x95EE;&#x9898;&#x5176;&#x5B9E;&#x90FD;&#x662F;&#x5728;&#x5E72;&#x8FD9;&#x4E2A;&#x4E8B;&#x513F;&#x3002;</strong></p>
<p>&#x628A;&#x67AF;&#x71E5;&#x7684;&#x672C;&#x8D28;&#x641E;&#x6E05;&#x695A;&#x4E86;&#xFF0C;&#x518D;&#x53BB;&#x6B23;&#x8D4F;&#x5404;&#x79CD;&#x95EE;&#x9898;&#x7684;&#x5305;&#x88C5;&#x624D;&#x80FD;&#x80F8;&#x6709;&#x6210;&#x7AF9;&#x561B;&#x3002;</p>
<p>&#x8FD9;&#x4E2A;&#x5E7F;&#x4E49;&#x7684;&#x63CF;&#x8FF0;&#x53EF;&#x4EE5;&#x6709;&#x5404;&#x79CD;&#x53D8;&#x4F53;&#xFF0C;&#x6BD4;&#x5982;&#x8D70;&#x8FF7;&#x5BAB;&#xFF0C;&#x6709;&#x7684;&#x683C;&#x5B50;&#x662F;&#x56F4;&#x5899;&#x4E0D;&#x80FD;&#x8D70;&#xFF0C;&#x4ECE;&#x8D77;&#x70B9;&#x5230;&#x7EC8;&#x70B9;&#x7684;&#x6700;&#x77ED;&#x8DDD;&#x79BB;&#x662F;&#x591A;&#x5C11;&#xFF1F;&#x5982;&#x679C;&#x8FD9;&#x4E2A;&#x8FF7;&#x5BAB;&#x5E26;&#x300C;&#x4F20;&#x9001;&#x95E8;&#x300D;&#x53EF;&#x4EE5;&#x77AC;&#x95F4;&#x4F20;&#x9001;&#x5462;&#xFF1F;</p>
<p>&#x518D;&#x6BD4;&#x5982;&#x8BF4;&#x4E24;&#x4E2A;&#x5355;&#x8BCD;&#xFF0C;&#x8981;&#x6C42;&#x4F60;&#x901A;&#x8FC7;&#x67D0;&#x4E9B;&#x66FF;&#x6362;&#xFF0C;&#x628A;&#x5176;&#x4E2D;&#x4E00;&#x4E2A;&#x53D8;&#x6210;&#x53E6;&#x4E00;&#x4E2A;&#xFF0C;&#x6BCF;&#x6B21;&#x53EA;&#x80FD;&#x66FF;&#x6362;&#x4E00;&#x4E2A;&#x5B57;&#x7B26;&#xFF0C;&#x6700;&#x5C11;&#x8981;&#x66FF;&#x6362;&#x51E0;&#x6B21;&#xFF1F;</p>
<p>&#x518D;&#x6BD4;&#x5982;&#x8BF4;&#x8FDE;&#x8FDE;&#x770B;&#x6E38;&#x620F;&#xFF0C;&#x4E24;&#x4E2A;&#x65B9;&#x5757;&#x6D88;&#x9664;&#x7684;&#x6761;&#x4EF6;&#x4E0D;&#x4EC5;&#x4EC5;&#x662F;&#x56FE;&#x6848;&#x76F8;&#x540C;&#xFF0C;&#x8FD8;&#x5F97;&#x4FDD;&#x8BC1;&#x4E24;&#x4E2A;&#x65B9;&#x5757;&#x4E4B;&#x95F4;&#x7684;&#x6700;&#x77ED;&#x8FDE;&#x7EBF;&#x4E0D;&#x80FD;&#x591A;&#x4E8E;&#x4E24;&#x4E2A;&#x62D0;&#x70B9;&#x3002;&#x4F60;&#x73A9;&#x8FDE;&#x8FDE;&#x770B;&#xFF0C;&#x70B9;&#x51FB;&#x4E24;&#x4E2A;&#x5750;&#x6807;&#xFF0C;&#x6E38;&#x620F;&#x662F;&#x5982;&#x4F55;&#x5224;&#x65AD;&#x5B83;&#x4FE9;&#x7684;&#x6700;&#x77ED;&#x8FDE;&#x7EBF;&#x6709;&#x51E0;&#x4E2A;&#x62D0;&#x70B9;&#x7684;&#xFF1F;</p>
<p>&#x518D;&#x6BD4;&#x5982;&#x2026;&#x2026;</p>
<p>&#x51C0;&#x6574;&#x4E9B;&#x82B1;&#x91CC;&#x80E1;&#x54E8;&#x7684;&#xFF0C;&#x8FD9;&#x4E9B;&#x95EE;&#x9898;&#x90FD;&#x6CA1;&#x5565;&#x5947;&#x6280;&#x6DEB;&#x5DE7;&#xFF0C;&#x672C;&#x8D28;&#x4E0A;&#x5C31;&#x662F;&#x4E00;&#x5E45;&#x300C;&#x56FE;&#x300D;&#xFF0C;&#x8BA9;&#x4F60;&#x4ECE;&#x4E00;&#x4E2A;&#x8D77;&#x70B9;&#xFF0C;&#x8D70;&#x5230;&#x7EC8;&#x70B9;&#xFF0C;&#x95EE;&#x6700;&#x77ED;&#x8DEF;&#x5F84;&#x3002;&#x8FD9;&#x5C31;&#x662F; BFS &#x7684;&#x672C;&#x8D28;&#xFF0C;&#x6846;&#x67B6;&#x641E;&#x6E05;&#x695A;&#x4E86;&#x76F4;&#x63A5;&#x9ED8;&#x5199;&#x5C31;&#x597D;&#x3002;</p>
<p>&#x8BB0;&#x4F4F;&#x4E0B;&#x9762;&#x8FD9;&#x4E2A;&#x6846;&#x67B6;&#x5C31; OK &#x4E86;&#xFF1A;</p>
<pre><code>// &#x8BA1;&#x7B97;&#x4ECE;&#x8D77;&#x70B9; start &#x5230;&#x7EC8;&#x70B9; target &#x7684;&#x6700;&#x8FD1;&#x8DDD;&#x79BB;
int BFS(Node start, Node target) {
    Queue&lt;Node&gt; q; // &#x6838;&#x5FC3;&#x6570;&#x636E;&#x7ED3;&#x6784;
    Set&lt;Node&gt; visited; // &#x907F;&#x514D;&#x8D70;&#x56DE;&#x5934;&#x8DEF;

    q.offer(start); // &#x5C06;&#x8D77;&#x70B9;&#x52A0;&#x5165;&#x961F;&#x5217;
    visited.add(start);
    int step = 0; // &#x8BB0;&#x5F55;&#x6269;&#x6563;&#x7684;&#x6B65;&#x6570;

    while (q not empty) {
        int sz = q.size();
        /* &#x5C06;&#x5F53;&#x524D;&#x961F;&#x5217;&#x4E2D;&#x7684;&#x6240;&#x6709;&#x8282;&#x70B9;&#x5411;&#x56DB;&#x5468;&#x6269;&#x6563; */
        for (int i = 0; i &lt; sz; i++) {
            Node cur = q.poll();
            /* &#x5212;&#x91CD;&#x70B9;&#xFF1A;&#x8FD9;&#x91CC;&#x5224;&#x65AD;&#x662F;&#x5426;&#x5230;&#x8FBE;&#x7EC8;&#x70B9; */
            if (cur is target)
                return step;
            /* &#x5C06; cur &#x7684;&#x76F8;&#x90BB;&#x8282;&#x70B9;&#x52A0;&#x5165;&#x961F;&#x5217; */
            for (Node x : cur.adj())
                if (x not in visited) {
                    q.offer(x);
                    visited.add(x);
                }
        }
        /* &#x5212;&#x91CD;&#x70B9;&#xFF1A;&#x66F4;&#x65B0;&#x6B65;&#x6570;&#x5728;&#x8FD9;&#x91CC; */
        step++;
    }
}
</code></pre><p>&#x961F;&#x5217;<code>q</code>&#x5C31;&#x4E0D;&#x8BF4;&#x4E86;&#xFF0C;BFS &#x7684;&#x6838;&#x5FC3;&#x6570;&#x636E;&#x7ED3;&#x6784;&#xFF1B;<code>cur.adj()</code>&#x6CDB;&#x6307;<code>cur</code>&#x76F8;&#x90BB;&#x7684;&#x8282;&#x70B9;&#xFF0C;&#x6BD4;&#x5982;&#x8BF4;&#x4E8C;&#x7EF4;&#x6570;&#x7EC4;&#x4E2D;&#xFF0C;<code>cur</code>&#x4E0A;&#x4E0B;&#x5DE6;&#x53F3;&#x56DB;&#x9762;&#x7684;&#x4F4D;&#x7F6E;&#x5C31;&#x662F;&#x76F8;&#x90BB;&#x8282;&#x70B9;&#xFF1B;<code>visited</code>&#x7684;&#x4E3B;&#x8981;&#x4F5C;&#x7528;&#x662F;&#x9632;&#x6B62;&#x8D70;&#x56DE;&#x5934;&#x8DEF;&#xFF0C;&#x5927;&#x90E8;&#x5206;&#x65F6;&#x5019;&#x90FD;&#x662F;&#x5FC5;&#x987B;&#x7684;&#xFF0C;&#x4F46;&#x662F;&#x50CF;&#x4E00;&#x822C;&#x7684;&#x4E8C;&#x53C9;&#x6811;&#x7ED3;&#x6784;&#xFF0C;&#x6CA1;&#x6709;&#x5B50;&#x8282;&#x70B9;&#x5230;&#x7236;&#x8282;&#x70B9;&#x7684;&#x6307;&#x9488;&#xFF0C;&#x4E0D;&#x4F1A;&#x8D70;&#x56DE;&#x5934;&#x8DEF;&#x5C31;&#x4E0D;&#x9700;&#x8981;<code>visited</code>&#x3002;</p>
<h3 id="&#x4E8C;&#x3001;&#x4E8C;&#x53C9;&#x6811;&#x7684;&#x6700;&#x5C0F;&#x9AD8;&#x5EA6;"><a name="&#x4E8C;&#x3001;&#x4E8C;&#x53C9;&#x6811;&#x7684;&#x6700;&#x5C0F;&#x9AD8;&#x5EA6;" class="anchor-navigation-ex-anchor" href="#&#x4E8C;&#x3001;&#x4E8C;&#x53C9;&#x6811;&#x7684;&#x6700;&#x5C0F;&#x9AD8;&#x5EA6;"><i class="fa fa-link" aria-hidden="true"></i></a><a name="&#x4E8C;&#x3001;&#x4E8C;&#x53C9;&#x6811;&#x7684;&#x6700;&#x5C0F;&#x9AD8;&#x5EA6;" class="plugin-anchor" href="#&#x4E8C;&#x3001;&#x4E8C;&#x53C9;&#x6811;&#x7684;&#x6700;&#x5C0F;&#x9AD8;&#x5EA6;"><i class="fa fa-link" aria-hidden="true"></i></a>&#x4E8C;&#x3001;&#x4E8C;&#x53C9;&#x6811;&#x7684;&#x6700;&#x5C0F;&#x9AD8;&#x5EA6;</h3>
<p>&#x5148;&#x6765;&#x4E2A;&#x7B80;&#x5355;&#x7684;&#x95EE;&#x9898;&#x5B9E;&#x8DF5;&#x4E00;&#x4E0B; BFS &#x6846;&#x67B6;&#x5427;&#xFF0C;&#x5224;&#x65AD;&#x4E00;&#x68F5;&#x4E8C;&#x53C9;&#x6811;&#x7684;<strong>&#x6700;&#x5C0F;</strong>&#x9AD8;&#x5EA6;&#xFF0C;&#x8FD9;&#x4E5F;&#x662F; LeetCode &#x7B2C; 111 &#x9898;&#xFF0C;&#x770B;&#x4E00;&#x4E0B;&#x9898;&#x76EE;&#xFF1A;</p>
<p><img src="https://gitee.com/zisuu/picture/raw/master/img/20201227144245.png" alt="image-20201227144245281"></p>
<p>&#x600E;&#x4E48;&#x5957;&#x5230; BFS &#x7684;&#x6846;&#x67B6;&#x91CC;&#x5462;&#xFF1F;&#x9996;&#x5148;&#x660E;&#x786E;&#x4E00;&#x4E0B;&#x8D77;&#x70B9;<code>start</code>&#x548C;&#x7EC8;&#x70B9;<code>target</code>&#x662F;&#x4EC0;&#x4E48;&#xFF0C;&#x600E;&#x4E48;&#x5224;&#x65AD;&#x5230;&#x8FBE;&#x4E86;&#x7EC8;&#x70B9;&#xFF1F;</p>
<p><strong>&#x663E;&#x7136;&#x8D77;&#x70B9;&#x5C31;&#x662F;<code>root</code>&#x6839;&#x8282;&#x70B9;&#xFF0C;&#x7EC8;&#x70B9;&#x5C31;&#x662F;&#x6700;&#x9760;&#x8FD1;&#x6839;&#x8282;&#x70B9;&#x7684;&#x90A3;&#x4E2A;&#x300C;&#x53F6;&#x5B50;&#x8282;&#x70B9;&#x300D;&#x561B;</strong>&#xFF0C;&#x53F6;&#x5B50;&#x8282;&#x70B9;&#x5C31;&#x662F;&#x4E24;&#x4E2A;&#x5B50;&#x8282;&#x70B9;&#x90FD;&#x662F;<code>null</code>&#x7684;&#x8282;&#x70B9;&#xFF1A;</p>
<pre><code>if (cur.left == null &amp;&amp; cur.right == null) 
    // &#x5230;&#x8FBE;&#x53F6;&#x5B50;&#x8282;&#x70B9;
</code></pre><p>&#x90A3;&#x4E48;&#xFF0C;&#x6309;&#x7167;&#x6211;&#x4EEC;&#x4E0A;&#x8FF0;&#x7684;&#x6846;&#x67B6;&#x7A0D;&#x52A0;&#x6539;&#x9020;&#x6765;&#x5199;&#x89E3;&#x6CD5;&#x5373;&#x53EF;&#xFF1A;</p>
<pre><code class="lang-java"><span class="hljs-function"><span class="hljs-keyword">int</span> <span class="hljs-title">minDepth</span><span class="hljs-params">(TreeNode root)</span> </span>{
    <span class="hljs-keyword">if</span> (root == <span class="hljs-keyword">null</span>) <span class="hljs-keyword">return</span> <span class="hljs-number">0</span>;
    Queue&lt;TreeNode&gt; q = <span class="hljs-keyword">new</span> LinkedList&lt;&gt;();
    q.offer(root);
    <span class="hljs-comment">// root &#x672C;&#x8EAB;&#x5C31;&#x662F;&#x4E00;&#x5C42;&#xFF0C;depth &#x521D;&#x59CB;&#x5316;&#x4E3A; 1</span>
    <span class="hljs-keyword">int</span> depth = <span class="hljs-number">1</span>;

    <span class="hljs-keyword">while</span> (!q.isEmpty()) {
        <span class="hljs-keyword">int</span> sz = q.size();
        <span class="hljs-comment">/* &#x5C06;&#x5F53;&#x524D;&#x961F;&#x5217;&#x4E2D;&#x7684;&#x6240;&#x6709;&#x8282;&#x70B9;&#x5411;&#x56DB;&#x5468;&#x6269;&#x6563; */</span>
        <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> i = <span class="hljs-number">0</span>; i &lt; sz; i++) {
            TreeNode cur = q.poll();
            <span class="hljs-comment">/* &#x5224;&#x65AD;&#x662F;&#x5426;&#x5230;&#x8FBE;&#x7EC8;&#x70B9; */</span>
            <span class="hljs-keyword">if</span> (cur.left == <span class="hljs-keyword">null</span> &amp;&amp; cur.right == <span class="hljs-keyword">null</span>) 
                <span class="hljs-keyword">return</span> depth;
            <span class="hljs-comment">/* &#x5C06; cur &#x7684;&#x76F8;&#x90BB;&#x8282;&#x70B9;&#x52A0;&#x5165;&#x961F;&#x5217; */</span>
            <span class="hljs-keyword">if</span> (cur.left != <span class="hljs-keyword">null</span>)
                q.offer(cur.left);
            <span class="hljs-keyword">if</span> (cur.right != <span class="hljs-keyword">null</span>) 
                q.offer(cur.right);
        }
        <span class="hljs-comment">/* &#x8FD9;&#x91CC;&#x589E;&#x52A0;&#x6B65;&#x6570; */</span>
        depth++;
    }
    <span class="hljs-keyword">return</span> depth;
}
</code></pre>
<p>&#x4E8C;&#x53C9;&#x6811;&#x662F;&#x5F88;&#x7B80;&#x5355;&#x7684;&#x6570;&#x636E;&#x7ED3;&#x6784;&#xFF0C;&#x6211;&#x60F3;&#x4E0A;&#x8FF0;&#x4EE3;&#x7801;&#x4F60;&#x5E94;&#x8BE5;&#x53EF;&#x4EE5;&#x7406;&#x89E3;&#x7684;&#x5427;&#xFF0C;&#x5176;&#x5B9E;&#x5176;&#x4ED6;&#x590D;&#x6742;&#x95EE;&#x9898;&#x90FD;&#x662F;&#x8FD9;&#x4E2A;&#x6846;&#x67B6;&#x7684;&#x53D8;&#x5F62;&#xFF0C;&#x5728;&#x63A2;&#x8BA8;&#x590D;&#x6742;&#x95EE;&#x9898;&#x4E4B;&#x524D;&#xFF0C;&#x6211;&#x4EEC;&#x89E3;&#x7B54;&#x4E24;&#x4E2A;&#x95EE;&#x9898;&#xFF1A;</p>
<p><strong>1&#x3001;&#x4E3A;&#x4EC0;&#x4E48; BFS &#x53EF;&#x4EE5;&#x627E;&#x5230;&#x6700;&#x77ED;&#x8DDD;&#x79BB;&#xFF0C;DFS &#x4E0D;&#x884C;&#x5417;</strong>&#xFF1F;</p>
<p>&#x9996;&#x5148;&#xFF0C;&#x4F60;&#x770B; BFS &#x7684;&#x903B;&#x8F91;&#xFF0C;<code>depth</code>&#x6BCF;&#x589E;&#x52A0;&#x4E00;&#x6B21;&#xFF0C;&#x961F;&#x5217;&#x4E2D;&#x7684;&#x6240;&#x6709;&#x8282;&#x70B9;&#x90FD;&#x5411;&#x524D;&#x8FC8;&#x4E00;&#x6B65;&#xFF0C;&#x8FD9;&#x4FDD;&#x8BC1;&#x4E86;&#x7B2C;&#x4E00;&#x6B21;&#x5230;&#x8FBE;&#x7EC8;&#x70B9;&#x7684;&#x65F6;&#x5019;&#xFF0C;&#x8D70;&#x7684;&#x6B65;&#x6570;&#x662F;&#x6700;&#x5C11;&#x7684;&#x3002;</p>
<p>DFS &#x4E0D;&#x80FD;&#x627E;&#x6700;&#x77ED;&#x8DEF;&#x5F84;&#x5417;&#xFF1F;&#x5176;&#x5B9E;&#x4E5F;&#x662F;&#x53EF;&#x4EE5;&#x7684;&#xFF0C;&#x4F46;&#x662F;&#x65F6;&#x95F4;&#x590D;&#x6742;&#x5EA6;&#x76F8;&#x5BF9;&#x9AD8;&#x5F88;&#x591A;&#x3002;</p>
<p>&#x4F60;&#x60F3;&#x554A;&#xFF0C;DFS &#x5B9E;&#x9645;&#x4E0A;&#x662F;&#x9760;&#x9012;&#x5F52;&#x7684;&#x5806;&#x6808;&#x8BB0;&#x5F55;&#x8D70;&#x8FC7;&#x7684;&#x8DEF;&#x5F84;&#xFF0C;&#x4F60;&#x8981;&#x627E;&#x5230;&#x6700;&#x77ED;&#x8DEF;&#x5F84;&#xFF0C;&#x80AF;&#x5B9A;&#x5F97;&#x628A;&#x4E8C;&#x53C9;&#x6811;&#x4E2D;&#x6240;&#x6709;&#x6811;&#x6748;&#x90FD;&#x63A2;&#x7D22;&#x5B8C;&#x624D;&#x80FD;&#x5BF9;&#x6BD4;&#x51FA;&#x6700;&#x77ED;&#x7684;&#x8DEF;&#x5F84;&#x6709;&#x591A;&#x957F;&#x5BF9;&#x4E0D;&#x5BF9;&#xFF1F;</p>
<p>&#x800C; BFS &#x501F;&#x52A9;&#x961F;&#x5217;&#x505A;&#x5230;&#x4E00;&#x6B21;&#x4E00;&#x6B65;&#x300C;&#x9F50;&#x5934;&#x5E76;&#x8FDB;&#x300D;&#xFF0C;&#x662F;&#x53EF;&#x4EE5;&#x5728;&#x4E0D;&#x904D;&#x5386;&#x5B8C;&#x6574;&#x68F5;&#x6811;&#x7684;&#x6761;&#x4EF6;&#x4E0B;&#x627E;&#x5230;&#x6700;&#x77ED;&#x8DDD;&#x79BB;&#x7684;&#x3002;</p>
<p>&#x5F62;&#x8C61;&#x70B9;&#x8BF4;&#xFF0C;DFS &#x662F;&#x7EBF;&#xFF0C;BFS &#x662F;&#x9762;&#xFF1B;DFS &#x662F;&#x5355;&#x6253;&#x72EC;&#x6597;&#xFF0C;BFS &#x662F;&#x96C6;&#x4F53;&#x884C;&#x52A8;&#x3002;&#x8FD9;&#x4E2A;&#x5E94;&#x8BE5;&#x6BD4;&#x8F83;&#x5BB9;&#x6613;&#x7406;&#x89E3;&#x5427;&#x3002;</p>
<p><strong>2&#x3001;&#x65E2;&#x7136; BFS &#x90A3;&#x4E48;&#x597D;&#xFF0C;&#x4E3A;&#x5565; DFS &#x8FD8;&#x8981;&#x5B58;&#x5728;</strong>&#xFF1F;</p>
<p>BFS &#x53EF;&#x4EE5;&#x627E;&#x5230;&#x6700;&#x77ED;&#x8DDD;&#x79BB;&#xFF0C;&#x4F46;&#x662F;&#x7A7A;&#x95F4;&#x590D;&#x6742;&#x5EA6;&#x9AD8;&#xFF0C;&#x800C; DFS &#x7684;&#x7A7A;&#x95F4;&#x590D;&#x6742;&#x5EA6;&#x8F83;&#x4F4E;&#x3002;</p>
<p>&#x8FD8;&#x662F;&#x62FF;&#x521A;&#x624D;&#x6211;&#x4EEC;&#x5904;&#x7406;&#x4E8C;&#x53C9;&#x6811;&#x95EE;&#x9898;&#x7684;&#x4F8B;&#x5B50;&#xFF0C;&#x5047;&#x8BBE;&#x7ED9;&#x4F60;&#x7684;&#x8FD9;&#x4E2A;&#x4E8C;&#x53C9;&#x6811;&#x662F;&#x6EE1;&#x4E8C;&#x53C9;&#x6811;&#xFF0C;&#x8282;&#x70B9;&#x603B;&#x6570;&#x4E3A;<code>N</code>&#xFF0C;&#x5BF9;&#x4E8E; DFS &#x7B97;&#x6CD5;&#x6765;&#x8BF4;&#xFF0C;&#x7A7A;&#x95F4;&#x590D;&#x6742;&#x5EA6;&#x65E0;&#x975E;&#x5C31;&#x662F;&#x9012;&#x5F52;&#x5806;&#x6808;&#xFF0C;&#x6700;&#x574F;&#x60C5;&#x51B5;&#x4E0B;&#x9876;&#x591A;&#x5C31;&#x662F;&#x6811;&#x7684;&#x9AD8;&#x5EA6;&#xFF0C;&#x4E5F;&#x5C31;&#x662F;<code>O(logN)</code>&#x3002;</p>
<p>&#x4F46;&#x662F;&#x4F60;&#x60F3;&#x60F3; BFS &#x7B97;&#x6CD5;&#xFF0C;&#x961F;&#x5217;&#x4E2D;&#x6BCF;&#x6B21;&#x90FD;&#x4F1A;&#x50A8;&#x5B58;&#x7740;&#x4E8C;&#x53C9;&#x6811;&#x4E00;&#x5C42;&#x7684;&#x8282;&#x70B9;&#xFF0C;&#x8FD9;&#x6837;&#x7684;&#x8BDD;&#x6700;&#x574F;&#x60C5;&#x51B5;&#x4E0B;&#x7A7A;&#x95F4;&#x590D;&#x6742;&#x5EA6;&#x5E94;&#x8BE5;&#x662F;&#x6811;&#x7684;&#x6700;&#x5E95;&#x5C42;&#x8282;&#x70B9;&#x7684;&#x6570;&#x91CF;&#xFF0C;&#x4E5F;&#x5C31;&#x662F;<code>N/2</code>&#xFF0C;&#x7528; Big O &#x8868;&#x793A;&#x7684;&#x8BDD;&#x4E5F;&#x5C31;&#x662F;<code>O(N)</code>&#x3002;</p>
<p>&#x7531;&#x6B64;&#x89C2;&#x4E4B;&#xFF0C;BFS &#x8FD8;&#x662F;&#x6709;&#x4EE3;&#x4EF7;&#x7684;&#xFF0C;&#x4E00;&#x822C;&#x6765;&#x8BF4;&#x5728;&#x627E;&#x6700;&#x77ED;&#x8DEF;&#x5F84;&#x7684;&#x65F6;&#x5019;&#x4F7F;&#x7528; BFS&#xFF0C;&#x5176;&#x4ED6;&#x65F6;&#x5019;&#x8FD8;&#x662F; DFS &#x4F7F;&#x7528;&#x5F97;&#x591A;&#x4E00;&#x4E9B;&#xFF08;&#x4E3B;&#x8981;&#x662F;&#x9012;&#x5F52;&#x4EE3;&#x7801;&#x597D;&#x5199;&#xFF09;&#x3002;</p>
<p>&#x597D;&#x4E86;&#xFF0C;&#x73B0;&#x5728;&#x4F60;&#x5BF9; BFS &#x4E86;&#x89E3;&#x5F97;&#x8DB3;&#x591F;&#x591A;&#x4E86;&#xFF0C;&#x4E0B;&#x9762;&#x6765;&#x4E00;&#x9053;&#x96BE;&#x4E00;&#x70B9;&#x7684;&#x9898;&#x76EE;&#xFF0C;&#x6DF1;&#x5316;&#x4E00;&#x4E0B;&#x6846;&#x67B6;&#x7684;&#x7406;&#x89E3;&#x5427;&#x3002;</p>
<h3 id="&#x4E09;&#x3001;&#x89E3;&#x5F00;&#x5BC6;&#x7801;&#x9501;&#x7684;&#x6700;&#x5C11;&#x6B21;&#x6570;"><a name="&#x4E09;&#x3001;&#x89E3;&#x5F00;&#x5BC6;&#x7801;&#x9501;&#x7684;&#x6700;&#x5C11;&#x6B21;&#x6570;" class="anchor-navigation-ex-anchor" href="#&#x4E09;&#x3001;&#x89E3;&#x5F00;&#x5BC6;&#x7801;&#x9501;&#x7684;&#x6700;&#x5C11;&#x6B21;&#x6570;"><i class="fa fa-link" aria-hidden="true"></i></a><a name="&#x4E09;&#x3001;&#x89E3;&#x5F00;&#x5BC6;&#x7801;&#x9501;&#x7684;&#x6700;&#x5C11;&#x6B21;&#x6570;" class="plugin-anchor" href="#&#x4E09;&#x3001;&#x89E3;&#x5F00;&#x5BC6;&#x7801;&#x9501;&#x7684;&#x6700;&#x5C11;&#x6B21;&#x6570;"><i class="fa fa-link" aria-hidden="true"></i></a>&#x4E09;&#x3001;&#x89E3;&#x5F00;&#x5BC6;&#x7801;&#x9501;&#x7684;&#x6700;&#x5C11;&#x6B21;&#x6570;</h3>
<p>&#x8FD9;&#x9053; LeetCode &#x9898;&#x76EE;&#x662F;&#x7B2C; 752 &#x9898;&#xFF0C;&#x6BD4;&#x8F83;&#x6709;&#x610F;&#x601D;&#xFF1A;</p>
<p><img src="https://gitee.com/zisuu/picture/raw/master/img/20201227144508.png" alt="image-20201227144508625"></p>
<p>&#x9898;&#x76EE;&#x4E2D;&#x63CF;&#x8FF0;&#x7684;&#x5C31;&#x662F;&#x6211;&#x4EEC;&#x751F;&#x6D3B;&#x4E2D;&#x5E38;&#x89C1;&#x7684;&#x90A3;&#x79CD;&#x5BC6;&#x7801;&#x9501;&#xFF0C;&#x82E5;&#x679C;&#x6CA1;&#x6709;&#x4EFB;&#x4F55;&#x7EA6;&#x675F;&#xFF0C;&#x6700;&#x5C11;&#x7684;&#x62E8;&#x52A8;&#x6B21;&#x6570;&#x5F88;&#x597D;&#x7B97;&#xFF0C;&#x5C31;&#x50CF;&#x6211;&#x4EEC;&#x5E73;&#x65F6;&#x5F00;&#x5BC6;&#x7801;&#x9501;&#x90A3;&#x6837;&#x76F4;&#x5954;&#x5BC6;&#x7801;&#x62E8;&#x5C31;&#x884C;&#x4E86;&#x3002;</p>
<p>&#x4F46;&#x73B0;&#x5728;&#x7684;&#x96BE;&#x70B9;&#x5C31;&#x5728;&#x4E8E;&#xFF0C;&#x4E0D;&#x80FD;&#x51FA;&#x73B0;<code>deadends</code>&#xFF0C;&#x5E94;&#x8BE5;&#x5982;&#x4F55;&#x8BA1;&#x7B97;&#x51FA;&#x6700;&#x5C11;&#x7684;&#x8F6C;&#x52A8;&#x6B21;&#x6570;&#x5462;&#xFF1F;</p>
<p><strong>&#x7B2C;&#x4E00;&#x6B65;&#xFF0C;&#x6211;&#x4EEC;&#x4E0D;&#x7BA1;&#x6240;&#x6709;&#x7684;&#x9650;&#x5236;&#x6761;&#x4EF6;&#xFF0C;&#x4E0D;&#x7BA1;<code>deadends</code>&#x548C;<code>target</code>&#x7684;&#x9650;&#x5236;&#xFF0C;&#x5C31;&#x601D;&#x8003;&#x4E00;&#x4E2A;&#x95EE;&#x9898;&#xFF1A;&#x5982;&#x679C;&#x8BA9;&#x4F60;&#x8BBE;&#x8BA1;&#x4E00;&#x4E2A;&#x7B97;&#x6CD5;&#xFF0C;&#x7A77;&#x4E3E;&#x6240;&#x6709;&#x53EF;&#x80FD;&#x7684;&#x5BC6;&#x7801;&#x7EC4;&#x5408;&#xFF0C;&#x4F60;&#x600E;&#x4E48;&#x505A;</strong>&#xFF1F;</p>
<p>&#x7A77;&#x4E3E;&#x5457;&#xFF0C;&#x518D;&#x7B80;&#x5355;&#x4E00;&#x70B9;&#xFF0C;&#x5982;&#x679C;&#x4F60;&#x53EA;&#x8F6C;&#x4E00;&#x4E0B;&#x9501;&#xFF0C;&#x6709;&#x51E0;&#x79CD;&#x53EF;&#x80FD;&#xFF1F;&#x603B;&#x5171;&#x6709; 4 &#x4E2A;&#x4F4D;&#x7F6E;&#xFF0C;&#x6BCF;&#x4E2A;&#x4F4D;&#x7F6E;&#x53EF;&#x4EE5;&#x5411;&#x4E0A;&#x8F6C;&#xFF0C;&#x4E5F;&#x53EF;&#x4EE5;&#x5411;&#x4E0B;&#x8F6C;&#xFF0C;&#x4E5F;&#x5C31;&#x662F;&#x6709; 8 &#x79CD;&#x53EF;&#x80FD;&#x5BF9;&#x5427;&#x3002;</p>
<p>&#x6BD4;&#x5982;&#x8BF4;&#x4ECE;<code>&quot;0000&quot;</code>&#x5F00;&#x59CB;&#xFF0C;&#x8F6C;&#x4E00;&#x6B21;&#xFF0C;&#x53EF;&#x4EE5;&#x7A77;&#x4E3E;&#x51FA;<code>&quot;1000&quot;, &quot;9000&quot;, &quot;0100&quot;, &quot;0900&quot;...</code>&#x5171; 8 &#x79CD;&#x5BC6;&#x7801;&#x3002;&#x7136;&#x540E;&#xFF0C;&#x518D;&#x4EE5;&#x8FD9; 8 &#x79CD;&#x5BC6;&#x7801;&#x4F5C;&#x4E3A;&#x57FA;&#x7840;&#xFF0C;&#x5BF9;&#x6BCF;&#x4E2A;&#x5BC6;&#x7801;&#x518D;&#x8F6C;&#x4E00;&#x4E0B;&#xFF0C;&#x7A77;&#x4E3E;&#x51FA;&#x6240;&#x6709;&#x53EF;&#x80FD;&#x2026;</p>
<p><strong>&#x4ED4;&#x7EC6;&#x60F3;&#x60F3;&#xFF0C;&#x8FD9;&#x5C31;&#x53EF;&#x4EE5;&#x62BD;&#x8C61;&#x6210;&#x4E00;&#x5E45;&#x56FE;&#xFF0C;&#x6BCF;&#x4E2A;&#x8282;&#x70B9;&#x6709; 8 &#x4E2A;&#x76F8;&#x90BB;&#x7684;&#x8282;&#x70B9;</strong>&#xFF0C;&#x53C8;&#x8BA9;&#x4F60;&#x6C42;&#x6700;&#x77ED;&#x8DDD;&#x79BB;&#xFF0C;&#x8FD9;&#x4E0D;&#x5C31;&#x662F;&#x5178;&#x578B;&#x7684; BFS &#x561B;&#xFF0C;&#x6846;&#x67B6;&#x5C31;&#x53EF;&#x4EE5;&#x6D3E;&#x4E0A;&#x7528;&#x573A;&#x4E86;&#xFF0C;&#x5148;&#x5199;&#x51FA;&#x4E00;&#x4E2A;&#x300C;&#x7B80;&#x964B;&#x300D;&#x7684; BFS &#x6846;&#x67B6;&#x4EE3;&#x7801;&#x518D;&#x8BF4;&#x522B;&#x7684;&#xFF1A;</p>
<pre><code class="lang-java"><span class="hljs-comment">// &#x5C06; s[j] &#x5411;&#x4E0A;&#x62E8;&#x52A8;&#x4E00;&#x6B21;</span>
<span class="hljs-function">String <span class="hljs-title">plusOne</span><span class="hljs-params">(String s, <span class="hljs-keyword">int</span> j)</span> </span>{
    <span class="hljs-keyword">char</span>[] ch = s.toCharArray();
    <span class="hljs-keyword">if</span> (ch[j] == <span class="hljs-string">&apos;9&apos;</span>)
        ch[j] = <span class="hljs-string">&apos;0&apos;</span>;
    <span class="hljs-keyword">else</span>
        ch[j] += <span class="hljs-number">1</span>;
    <span class="hljs-keyword">return</span> <span class="hljs-keyword">new</span> String(ch);
}
<span class="hljs-comment">// &#x5C06; s[i] &#x5411;&#x4E0B;&#x62E8;&#x52A8;&#x4E00;&#x6B21;</span>
<span class="hljs-function">String <span class="hljs-title">minusOne</span><span class="hljs-params">(String s, <span class="hljs-keyword">int</span> j)</span> </span>{
    <span class="hljs-keyword">char</span>[] ch = s.toCharArray();
    <span class="hljs-keyword">if</span> (ch[j] == <span class="hljs-string">&apos;0&apos;</span>)
        ch[j] = <span class="hljs-string">&apos;9&apos;</span>;
    <span class="hljs-keyword">else</span>
        ch[j] -= <span class="hljs-number">1</span>;
    <span class="hljs-keyword">return</span> <span class="hljs-keyword">new</span> String(ch);
}

<span class="hljs-comment">// BFS &#x6846;&#x67B6;&#xFF0C;&#x6253;&#x5370;&#x51FA;&#x6240;&#x6709;&#x53EF;&#x80FD;&#x7684;&#x5BC6;&#x7801;</span>
<span class="hljs-function"><span class="hljs-keyword">void</span> <span class="hljs-title">BFS</span><span class="hljs-params">(String target)</span> </span>{
    Queue&lt;String&gt; q = <span class="hljs-keyword">new</span> LinkedList&lt;&gt;();
    q.offer(<span class="hljs-string">&quot;0000&quot;</span>);

    <span class="hljs-keyword">while</span> (!q.isEmpty()) {
        <span class="hljs-keyword">int</span> sz = q.size();
        <span class="hljs-comment">/* &#x5C06;&#x5F53;&#x524D;&#x961F;&#x5217;&#x4E2D;&#x7684;&#x6240;&#x6709;&#x8282;&#x70B9;&#x5411;&#x5468;&#x56F4;&#x6269;&#x6563; */</span>
        <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> i = <span class="hljs-number">0</span>; i &lt; sz; i++) {
            String cur = q.poll();
            <span class="hljs-comment">/* &#x5224;&#x65AD;&#x662F;&#x5426;&#x5230;&#x8FBE;&#x7EC8;&#x70B9; */</span>
            System.out.println(cur);

            <span class="hljs-comment">/* &#x5C06;&#x4E00;&#x4E2A;&#x8282;&#x70B9;&#x7684;&#x76F8;&#x90BB;&#x8282;&#x70B9;&#x52A0;&#x5165;&#x961F;&#x5217; */</span>
            <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> j = <span class="hljs-number">0</span>; j &lt; <span class="hljs-number">4</span>; j++) {
                String up = plusOne(cur, j);
                String down = minusOne(cur, j);
                q.offer(up);
                q.offer(down);
            }
        }
        <span class="hljs-comment">/* &#x5728;&#x8FD9;&#x91CC;&#x589E;&#x52A0;&#x6B65;&#x6570; */</span>
    }
    <span class="hljs-keyword">return</span>;
}
</code></pre>
<p>PS&#xFF1A;&#x8FD9;&#x6BB5;&#x4EE3;&#x7801;&#x5F53;&#x7136;&#x6709;&#x5F88;&#x591A;&#x95EE;&#x9898;&#xFF0C;&#x4F46;&#x662F;&#x6211;&#x4EEC;&#x505A;&#x7B97;&#x6CD5;&#x9898;&#x80AF;&#x5B9A;&#x4E0D;&#x662F;&#x4E00;&#x8E74;&#x800C;&#x5C31;&#x7684;&#xFF0C;&#x800C;&#x662F;&#x4ECE;&#x7B80;&#x964B;&#x5230;&#x5B8C;&#x7F8E;&#x7684;&#x3002;&#x4E0D;&#x8981;&#x5B8C;&#x7F8E;&#x4E3B;&#x4E49;&#xFF0C;&#x54B1;&#x8981;&#x6162;&#x6162;&#x6765;&#xFF0C;&#x597D;&#x4E0D;&#x3002;</p>
<p><strong>&#x8FD9;&#x6BB5; BFS &#x4EE3;&#x7801;&#x5DF2;&#x7ECF;&#x80FD;&#x591F;&#x7A77;&#x4E3E;&#x6240;&#x6709;&#x53EF;&#x80FD;&#x7684;&#x5BC6;&#x7801;&#x7EC4;&#x5408;&#x4E86;&#xFF0C;&#x4F46;&#x662F;&#x663E;&#x7136;&#x4E0D;&#x80FD;&#x5B8C;&#x6210;&#x9898;&#x76EE;&#xFF0C;&#x6709;&#x5982;&#x4E0B;&#x95EE;&#x9898;&#x9700;&#x8981;&#x89E3;&#x51B3;</strong>&#xFF1A;</p>
<p>1&#x3001;&#x4F1A;&#x8D70;&#x56DE;&#x5934;&#x8DEF;&#x3002;&#x6BD4;&#x5982;&#x8BF4;&#x6211;&#x4EEC;&#x4ECE;<code>&quot;0000&quot;</code>&#x62E8;&#x5230;<code>&quot;1000&quot;</code>&#xFF0C;&#x4F46;&#x662F;&#x7B49;&#x4ECE;&#x961F;&#x5217;&#x62FF;&#x51FA;<code>&quot;1000&quot;</code>&#x65F6;&#xFF0C;&#x8FD8;&#x4F1A;&#x62E8;&#x51FA;&#x4E00;&#x4E2A;<code>&quot;0000&quot;</code>&#xFF0C;&#x8FD9;&#x6837;&#x7684;&#x8BDD;&#x4F1A;&#x4EA7;&#x751F;&#x6B7B;&#x5FAA;&#x73AF;&#x3002;</p>
<p>2&#x3001;&#x6CA1;&#x6709;&#x7EC8;&#x6B62;&#x6761;&#x4EF6;&#xFF0C;&#x6309;&#x7167;&#x9898;&#x76EE;&#x8981;&#x6C42;&#xFF0C;&#x6211;&#x4EEC;&#x627E;&#x5230;<code>target</code>&#x5C31;&#x5E94;&#x8BE5;&#x7ED3;&#x675F;&#x5E76;&#x8FD4;&#x56DE;&#x62E8;&#x52A8;&#x7684;&#x6B21;&#x6570;&#x3002;</p>
<p>3&#x3001;&#x6CA1;&#x6709;&#x5BF9;<code>deadends</code>&#x7684;&#x5904;&#x7406;&#xFF0C;&#x6309;&#x9053;&#x7406;&#x8FD9;&#x4E9B;&#x300C;&#x6B7B;&#x4EA1;&#x5BC6;&#x7801;&#x300D;&#x662F;&#x4E0D;&#x80FD;&#x51FA;&#x73B0;&#x7684;&#xFF0C;&#x4E5F;&#x5C31;&#x662F;&#x8BF4;&#x4F60;&#x9047;&#x5230;&#x8FD9;&#x4E9B;&#x5BC6;&#x7801;&#x7684;&#x65F6;&#x5019;&#x9700;&#x8981;&#x8DF3;&#x8FC7;&#x3002;</p>
<p>&#x5982;&#x679C;&#x4F60;&#x80FD;&#x591F;&#x770B;&#x61C2;&#x4E0A;&#x9762;&#x90A3;&#x6BB5;&#x4EE3;&#x7801;&#xFF0C;&#x771F;&#x5F97;&#x7ED9;&#x4F60;&#x9F13;&#x638C;&#xFF0C;&#x53EA;&#x8981;&#x6309;&#x7167; BFS &#x6846;&#x67B6;&#x5728;&#x5BF9;&#x5E94;&#x7684;&#x4F4D;&#x7F6E;&#x7A0D;&#x4F5C;&#x4FEE;&#x6539;&#x5373;&#x53EF;&#x4FEE;&#x590D;&#x8FD9;&#x4E9B;&#x95EE;&#x9898;&#xFF1A;</p>
<pre><code>int openLock(String[] deadends, String target) {
    // &#x8BB0;&#x5F55;&#x9700;&#x8981;&#x8DF3;&#x8FC7;&#x7684;&#x6B7B;&#x4EA1;&#x5BC6;&#x7801;
    Set&lt;String&gt; deads = new HashSet&lt;&gt;();
    for (String s : deadends) deads.add(s);
    // &#x8BB0;&#x5F55;&#x5DF2;&#x7ECF;&#x7A77;&#x4E3E;&#x8FC7;&#x7684;&#x5BC6;&#x7801;&#xFF0C;&#x9632;&#x6B62;&#x8D70;&#x56DE;&#x5934;&#x8DEF;
    Set&lt;String&gt; visited = new HashSet&lt;&gt;();
    Queue&lt;String&gt; q = new LinkedList&lt;&gt;();
    // &#x4ECE;&#x8D77;&#x70B9;&#x5F00;&#x59CB;&#x542F;&#x52A8;&#x5E7F;&#x5EA6;&#x4F18;&#x5148;&#x641C;&#x7D22;
    int step = 0;
    q.offer(&quot;0000&quot;);
    visited.add(&quot;0000&quot;);

    while (!q.isEmpty()) {
        int sz = q.size();
        /* &#x5C06;&#x5F53;&#x524D;&#x961F;&#x5217;&#x4E2D;&#x7684;&#x6240;&#x6709;&#x8282;&#x70B9;&#x5411;&#x5468;&#x56F4;&#x6269;&#x6563; */
        for (int i = 0; i &lt; sz; i++) {
            String cur = q.poll();

            /* &#x5224;&#x65AD;&#x662F;&#x5426;&#x5230;&#x8FBE;&#x7EC8;&#x70B9; */
            if (deads.contains(cur))
                continue;
            if (cur.equals(target))
                return step;

            /* &#x5C06;&#x4E00;&#x4E2A;&#x8282;&#x70B9;&#x7684;&#x672A;&#x904D;&#x5386;&#x76F8;&#x90BB;&#x8282;&#x70B9;&#x52A0;&#x5165;&#x961F;&#x5217; */
            for (int j = 0; j &lt; 4; j++) {
                String up = plusOne(cur, j);
                if (!visited.contains(up)) {
                    q.offer(up);
                    visited.add(up);
                }
                String down = minusOne(cur, j);
                if (!visited.contains(down)) {
                    q.offer(down);
                    visited.add(down);
                }
            }
        }
        /* &#x5728;&#x8FD9;&#x91CC;&#x589E;&#x52A0;&#x6B65;&#x6570; */
        step++;
    }
    // &#x5982;&#x679C;&#x7A77;&#x4E3E;&#x5B8C;&#x90FD;&#x6CA1;&#x627E;&#x5230;&#x76EE;&#x6807;&#x5BC6;&#x7801;&#xFF0C;&#x90A3;&#x5C31;&#x662F;&#x627E;&#x4E0D;&#x5230;&#x4E86;
    return -1;
}
</code></pre><p>&#x81F3;&#x6B64;&#xFF0C;&#x6211;&#x4EEC;&#x5C31;&#x89E3;&#x51B3;&#x8FD9;&#x9053;&#x9898;&#x76EE;&#x4E86;&#x3002;&#x6709;&#x4E00;&#x4E2A;&#x6BD4;&#x8F83;&#x5C0F;&#x7684;&#x4F18;&#x5316;&#xFF1A;&#x53EF;&#x4EE5;&#x4E0D;&#x9700;&#x8981;<code>dead</code>&#x8FD9;&#x4E2A;&#x54C8;&#x5E0C;&#x96C6;&#x5408;&#xFF0C;&#x53EF;&#x4EE5;&#x76F4;&#x63A5;&#x5C06;&#x8FD9;&#x4E9B;&#x5143;&#x7D20;&#x521D;&#x59CB;&#x5316;&#x5230;<code>visited</code>&#x96C6;&#x5408;&#x4E2D;&#xFF0C;&#x6548;&#x679C;&#x662F;&#x4E00;&#x6837;&#x7684;&#xFF0C;&#x53EF;&#x80FD;&#x66F4;&#x52A0;&#x4F18;&#x96C5;&#x4E00;&#x4E9B;&#x3002;</p>
<h3 id="&#x56DB;&#x3001;&#x53CC;&#x5411;-bfs-&#x4F18;&#x5316;"><a name="&#x56DB;&#x3001;&#x53CC;&#x5411;-bfs-&#x4F18;&#x5316;" class="anchor-navigation-ex-anchor" href="#&#x56DB;&#x3001;&#x53CC;&#x5411;-bfs-&#x4F18;&#x5316;"><i class="fa fa-link" aria-hidden="true"></i></a><a name="&#x56DB;&#x3001;&#x53CC;&#x5411;-bfs-&#x4F18;&#x5316;" class="plugin-anchor" href="#&#x56DB;&#x3001;&#x53CC;&#x5411;-bfs-&#x4F18;&#x5316;"><i class="fa fa-link" aria-hidden="true"></i></a>&#x56DB;&#x3001;&#x53CC;&#x5411; BFS &#x4F18;&#x5316;</h3>
<p>&#x4F60;&#x4EE5;&#x4E3A;&#x5230;&#x8FD9;&#x91CC; BFS &#x7B97;&#x6CD5;&#x5C31;&#x7ED3;&#x675F;&#x4E86;&#xFF1F;&#x6070;&#x6070;&#x76F8;&#x53CD;&#x3002;BFS &#x7B97;&#x6CD5;&#x8FD8;&#x6709;&#x4E00;&#x79CD;&#x7A0D;&#x5FAE;&#x9AD8;&#x7EA7;&#x4E00;&#x70B9;&#x7684;&#x4F18;&#x5316;&#x601D;&#x8DEF;&#xFF1A;<strong>&#x53CC;&#x5411; BFS</strong>&#xFF0C;&#x53EF;&#x4EE5;&#x8FDB;&#x4E00;&#x6B65;&#x63D0;&#x9AD8;&#x7B97;&#x6CD5;&#x7684;&#x6548;&#x7387;&#x3002;</p>
<p>&#x7BC7;&#x5E45;&#x6240;&#x9650;&#xFF0C;&#x8FD9;&#x91CC;&#x5C31;&#x63D0;&#x4E00;&#x4E0B;&#x533A;&#x522B;&#xFF1A;<strong>&#x4F20;&#x7EDF;&#x7684; BFS &#x6846;&#x67B6;&#x5C31;&#x662F;&#x4ECE;&#x8D77;&#x70B9;&#x5F00;&#x59CB;&#x5411;&#x56DB;&#x5468;&#x6269;&#x6563;&#xFF0C;&#x9047;&#x5230;&#x7EC8;&#x70B9;&#x65F6;&#x505C;&#x6B62;&#xFF1B;&#x800C;&#x53CC;&#x5411; BFS &#x5219;&#x662F;&#x4ECE;&#x8D77;&#x70B9;&#x548C;&#x7EC8;&#x70B9;&#x540C;&#x65F6;&#x5F00;&#x59CB;&#x6269;&#x6563;&#xFF0C;&#x5F53;&#x4E24;&#x8FB9;&#x6709;&#x4EA4;&#x96C6;&#x7684;&#x65F6;&#x5019;&#x505C;&#x6B62;</strong>&#x3002;</p>
<p>&#x4E3A;&#x4EC0;&#x4E48;&#x8FD9;&#x6837;&#x80FD;&#x591F;&#x80FD;&#x591F;&#x63D0;&#x5347;&#x6548;&#x7387;&#x5462;&#xFF1F;&#x5176;&#x5B9E;&#x4ECE; Big O &#x8868;&#x793A;&#x6CD5;&#x5206;&#x6790;&#x7B97;&#x6CD5;&#x590D;&#x6742;&#x5EA6;&#x7684;&#x8BDD;&#xFF0C;&#x5B83;&#x4FE9;&#x7684;&#x6700;&#x574F;&#x590D;&#x6742;&#x5EA6;&#x90FD;&#x662F;<code>O(N)</code>&#xFF0C;&#x4F46;&#x662F;&#x5B9E;&#x9645;&#x4E0A;&#x53CC;&#x5411; BFS &#x786E;&#x5B9E;&#x4F1A;&#x5FEB;&#x4E00;&#x4E9B;&#xFF0C;&#x6211;&#x7ED9;&#x4F60;&#x753B;&#x4E24;&#x5F20;&#x56FE;&#x770B;&#x4E00;&#x773C;&#x5C31;&#x660E;&#x767D;&#x4E86;&#xFF1A;</p>
<p><img src="https://gitee.com/zisuu/picture/raw/master/img/20201227145409.png" alt="image-20201227145409025"></p>
<p><img src="https://gitee.com/zisuu/picture/raw/master/img/20201227145422.png" alt="image-20201227145422732"></p>
<p>&#x56FE;&#x793A;&#x4E2D;&#x7684;&#x6811;&#x5F62;&#x7ED3;&#x6784;&#xFF0C;&#x5982;&#x679C;&#x7EC8;&#x70B9;&#x5728;&#x6700;&#x5E95;&#x90E8;&#xFF0C;&#x6309;&#x7167;&#x4F20;&#x7EDF; BFS &#x7B97;&#x6CD5;&#x7684;&#x7B56;&#x7565;&#xFF0C;&#x4F1A;&#x628A;&#x6574;&#x68F5;&#x6811;&#x7684;&#x8282;&#x70B9;&#x90FD;&#x641C;&#x7D22;&#x4E00;&#x904D;&#xFF0C;&#x6700;&#x540E;&#x627E;&#x5230;<code>target</code>&#xFF1B;&#x800C;&#x53CC;&#x5411; BFS &#x5176;&#x5B9E;&#x53EA;&#x904D;&#x5386;&#x4E86;&#x534A;&#x68F5;&#x6811;&#x5C31;&#x51FA;&#x73B0;&#x4E86;&#x4EA4;&#x96C6;&#xFF0C;&#x4E5F;&#x5C31;&#x662F;&#x627E;&#x5230;&#x4E86;&#x6700;&#x77ED;&#x8DDD;&#x79BB;&#x3002;&#x4ECE;&#x8FD9;&#x4E2A;&#x4F8B;&#x5B50;&#x53EF;&#x4EE5;&#x76F4;&#x89C2;&#x5730;&#x611F;&#x53D7;&#x5230;&#xFF0C;&#x53CC;&#x5411; BFS &#x662F;&#x8981;&#x6BD4;&#x4F20;&#x7EDF; BFS &#x9AD8;&#x6548;&#x7684;&#x3002;</p>
<p><strong>&#x4E0D;&#x8FC7;&#xFF0C;&#x53CC;&#x5411; BFS &#x4E5F;&#x6709;&#x5C40;&#x9650;&#xFF0C;&#x56E0;&#x4E3A;&#x4F60;&#x5FC5;&#x987B;&#x77E5;&#x9053;&#x7EC8;&#x70B9;&#x5728;&#x54EA;&#x91CC;</strong>&#x3002;&#x6BD4;&#x5982;&#x6211;&#x4EEC;&#x521A;&#x624D;&#x8BA8;&#x8BBA;&#x7684;&#x4E8C;&#x53C9;&#x6811;&#x6700;&#x5C0F;&#x9AD8;&#x5EA6;&#x7684;&#x95EE;&#x9898;&#xFF0C;&#x4F60;&#x4E00;&#x5F00;&#x59CB;&#x6839;&#x672C;&#x5C31;&#x4E0D;&#x77E5;&#x9053;&#x7EC8;&#x70B9;&#x5728;&#x54EA;&#x91CC;&#xFF0C;&#x4E5F;&#x5C31;&#x65E0;&#x6CD5;&#x4F7F;&#x7528;&#x53CC;&#x5411; BFS&#xFF1B;&#x4F46;&#x662F;&#x7B2C;&#x4E8C;&#x4E2A;&#x5BC6;&#x7801;&#x9501;&#x7684;&#x95EE;&#x9898;&#xFF0C;&#x662F;&#x53EF;&#x4EE5;&#x4F7F;&#x7528;&#x53CC;&#x5411; BFS &#x7B97;&#x6CD5;&#x6765;&#x63D0;&#x9AD8;&#x6548;&#x7387;&#x7684;&#xFF0C;&#x4EE3;&#x7801;&#x7A0D;&#x52A0;&#x4FEE;&#x6539;&#x5373;&#x53EF;&#xFF1A;</p>
<pre><code>int openLock(String[] deadends, String target) {
    Set&lt;String&gt; deads = new HashSet&lt;&gt;();
    for (String s : deadends) deads.add(s);
    // &#x7528;&#x96C6;&#x5408;&#x4E0D;&#x7528;&#x961F;&#x5217;&#xFF0C;&#x53EF;&#x4EE5;&#x5FEB;&#x901F;&#x5224;&#x65AD;&#x5143;&#x7D20;&#x662F;&#x5426;&#x5B58;&#x5728;
    Set&lt;String&gt; q1 = new HashSet&lt;&gt;();
    Set&lt;String&gt; q2 = new HashSet&lt;&gt;();
    Set&lt;String&gt; visited = new HashSet&lt;&gt;();

    int step = 0;
    q1.add(&quot;0000&quot;);
    q2.add(target);

    while (!q1.isEmpty() &amp;&amp; !q2.isEmpty()) {
        // &#x54C8;&#x5E0C;&#x96C6;&#x5408;&#x5728;&#x904D;&#x5386;&#x7684;&#x8FC7;&#x7A0B;&#x4E2D;&#x4E0D;&#x80FD;&#x4FEE;&#x6539;&#xFF0C;&#x7528; temp &#x5B58;&#x50A8;&#x6269;&#x6563;&#x7ED3;&#x679C;
        Set&lt;String&gt; temp = new HashSet&lt;&gt;();

        /* &#x5C06; q1 &#x4E2D;&#x7684;&#x6240;&#x6709;&#x8282;&#x70B9;&#x5411;&#x5468;&#x56F4;&#x6269;&#x6563; */
        for (String cur : q1) {
            /* &#x5224;&#x65AD;&#x662F;&#x5426;&#x5230;&#x8FBE;&#x7EC8;&#x70B9; */
            if (deads.contains(cur))
                continue;
            if (q2.contains(cur))
                return step;
            visited.add(cur);

            /* &#x5C06;&#x4E00;&#x4E2A;&#x8282;&#x70B9;&#x7684;&#x672A;&#x904D;&#x5386;&#x76F8;&#x90BB;&#x8282;&#x70B9;&#x52A0;&#x5165;&#x96C6;&#x5408; */
            for (int j = 0; j &lt; 4; j++) {
                String up = plusOne(cur, j);
                if (!visited.contains(up))
                    temp.add(up);
                String down = minusOne(cur, j);
                if (!visited.contains(down))
                    temp.add(down);
            }
        }
        /* &#x5728;&#x8FD9;&#x91CC;&#x589E;&#x52A0;&#x6B65;&#x6570; */
        step++;
        // temp &#x76F8;&#x5F53;&#x4E8E; q1
        // &#x8FD9;&#x91CC;&#x4EA4;&#x6362; q1 q2&#xFF0C;&#x4E0B;&#x4E00;&#x8F6E; while &#x5C31;&#x662F;&#x6269;&#x6563; q2
        q1 = q2;
        q2 = temp;
    }
    return -1;
}
</code></pre><p>&#x53CC;&#x5411; BFS &#x8FD8;&#x662F;&#x9075;&#x5FAA; BFS &#x7B97;&#x6CD5;&#x6846;&#x67B6;&#x7684;&#xFF0C;&#x53EA;&#x662F;<strong>&#x4E0D;&#x518D;&#x4F7F;&#x7528;&#x961F;&#x5217;&#xFF0C;&#x800C;&#x662F;&#x4F7F;&#x7528; HashSet &#x65B9;&#x4FBF;&#x5FEB;&#x901F;&#x5224;&#x65AD;&#x4E24;&#x4E2A;&#x96C6;&#x5408;&#x662F;&#x5426;&#x6709;&#x4EA4;&#x96C6;</strong>&#x3002;</p>
<p>&#x53E6;&#x5916;&#x7684;&#x4E00;&#x4E2A;&#x6280;&#x5DE7;&#x70B9;&#x5C31;&#x662F; <strong>while &#x5FAA;&#x73AF;&#x7684;&#x6700;&#x540E;&#x4EA4;&#x6362;<code>q1</code>&#x548C;<code>q2</code>&#x7684;&#x5185;&#x5BB9;</strong>&#xFF0C;&#x6240;&#x4EE5;&#x53EA;&#x8981;&#x9ED8;&#x8BA4;&#x6269;&#x6563;<code>q1</code>&#x5C31;&#x76F8;&#x5F53;&#x4E8E;&#x8F6E;&#x6D41;&#x6269;&#x6563;<code>q1</code>&#x548C;<code>q2</code>&#x3002;</p>
<p>&#x5176;&#x5B9E;&#x53CC;&#x5411; BFS &#x8FD8;&#x6709;&#x4E00;&#x4E2A;&#x4F18;&#x5316;&#xFF0C;&#x5C31;&#x662F;&#x5728; while &#x5FAA;&#x73AF;&#x5F00;&#x59CB;&#x65F6;&#x505A;&#x4E00;&#x4E2A;&#x5224;&#x65AD;&#xFF1A;</p>
<pre><code>// ...
while (!q1.isEmpty() &amp;&amp; !q2.isEmpty()) {
    if (q1.size() &gt; q2.size()) {
        // &#x4EA4;&#x6362; q1 &#x548C; q2
        temp = q1;
        q1 = q2;
        q2 = temp;
    }
    // ...
</code></pre><p>&#x4E3A;&#x4EC0;&#x4E48;&#x8FD9;&#x662F;&#x4E00;&#x4E2A;&#x4F18;&#x5316;&#x5462;&#xFF1F;</p>
<p>&#x56E0;&#x4E3A;&#x6309;&#x7167; BFS &#x7684;&#x903B;&#x8F91;&#xFF0C;&#x961F;&#x5217;&#xFF08;&#x96C6;&#x5408;&#xFF09;&#x4E2D;&#x7684;&#x5143;&#x7D20;&#x8D8A;&#x591A;&#xFF0C;&#x6269;&#x6563;&#x4E4B;&#x540E;&#x65B0;&#x7684;&#x961F;&#x5217;&#xFF08;&#x96C6;&#x5408;&#xFF09;&#x4E2D;&#x7684;&#x5143;&#x7D20;&#x5C31;&#x8D8A;&#x591A;&#xFF1B;&#x5728;&#x53CC;&#x5411; BFS &#x7B97;&#x6CD5;&#x4E2D;&#xFF0C;&#x5982;&#x679C;&#x6211;&#x4EEC;&#x6BCF;&#x6B21;&#x90FD;&#x9009;&#x62E9;&#x4E00;&#x4E2A;&#x8F83;&#x5C0F;&#x7684;&#x96C6;&#x5408;&#x8FDB;&#x884C;&#x6269;&#x6563;&#xFF0C;&#x90A3;&#x4E48;&#x5360;&#x7528;&#x7684;&#x7A7A;&#x95F4;&#x589E;&#x957F;&#x901F;&#x5EA6;&#x5C31;&#x4F1A;&#x6162;&#x4E00;&#x4E9B;&#xFF0C;&#x6548;&#x7387;&#x5C31;&#x4F1A;&#x9AD8;&#x4E00;&#x4E9B;&#x3002;</p>
<p>&#x4E0D;&#x8FC7;&#x8BDD;&#x8BF4;&#x56DE;&#x6765;&#xFF0C;<strong>&#x65E0;&#x8BBA;&#x4F20;&#x7EDF; BFS &#x8FD8;&#x662F;&#x53CC;&#x5411; BFS&#xFF0C;&#x65E0;&#x8BBA;&#x505A;&#x4E0D;&#x505A;&#x4F18;&#x5316;&#xFF0C;&#x4ECE; Big O &#x8861;&#x91CF;&#x6807;&#x51C6;&#x6765;&#x770B;&#xFF0C;&#x7A7A;&#x95F4;&#x590D;&#x6742;&#x5EA6;&#x90FD;&#x662F;&#x4E00;&#x6837;&#x7684;</strong>&#xFF0C;&#x53EA;&#x80FD;&#x8BF4;&#x53CC;&#x5411; BFS &#x662F;&#x4E00;&#x79CD; trick &#x5427;&#xFF0C;&#x638C;&#x63E1;&#x4E0D;&#x638C;&#x63E1;&#x5176;&#x5B9E;&#x90FD;&#x65E0;&#x6240;&#x8C13;&#x3002;&#x6700;&#x5173;&#x952E;&#x7684;&#x662F;&#x628A; BFS &#x901A;&#x7528;&#x6846;&#x67B6;&#x8BB0;&#x4E0B;&#x6765;&#xFF0C;&#x53CD;&#x6B63;&#x6240;&#x6709; BFS &#x7B97;&#x6CD5;&#x90FD;&#x53EF;&#x4EE5;&#x7528;&#x5B83;&#x5957;&#x51FA;&#x89E3;&#x6CD5;&#x3002;</p>
<h2 id="&#x4E8C;-&#x5229;&#x7528;bfs&#x5DE7;&#x89E3;&#x76CA;&#x667A;&#x6E38;&#x620F;"><a name="&#x4E8C;-&#x5229;&#x7528;bfs&#x5DE7;&#x89E3;&#x76CA;&#x667A;&#x6E38;&#x620F;" class="anchor-navigation-ex-anchor" href="#&#x4E8C;-&#x5229;&#x7528;bfs&#x5DE7;&#x89E3;&#x76CA;&#x667A;&#x6E38;&#x620F;"><i class="fa fa-link" aria-hidden="true"></i></a><a name="&#x4E8C;-&#x5229;&#x7528;bfs&#x5DE7;&#x89E3;&#x76CA;&#x667A;&#x6E38;&#x620F;" class="plugin-anchor" href="#&#x4E8C;-&#x5229;&#x7528;bfs&#x5DE7;&#x89E3;&#x76CA;&#x667A;&#x6E38;&#x620F;"><i class="fa fa-link" aria-hidden="true"></i></a>&#x4E8C; &#x5229;&#x7528;bfs&#x5DE7;&#x89E3;&#x76CA;&#x667A;&#x6E38;&#x620F;</h2>
<p>&#x6ED1;&#x52A8;&#x62FC;&#x56FE;&#x6E38;&#x620F;&#x5927;&#x5BB6;&#x5E94;&#x8BE5;&#x90FD;&#x73A9;&#x8FC7;&#xFF0C;&#x4E0B;&#x56FE;&#x662F;&#x4E00;&#x4E2A; 4x4 &#x7684;&#x6ED1;&#x52A8;&#x62FC;&#x56FE;&#xFF1A;</p>
<p><img src="https://gitee.com/zisuu/picture/raw/master/img/20201227152528.png" alt="image-20201227152528411"></p>
<p>&#x62FC;&#x56FE;&#x4E2D;&#x6709;&#x4E00;&#x4E2A;&#x683C;&#x5B50;&#x662F;&#x7A7A;&#x7684;&#xFF0C;&#x53EF;&#x4EE5;&#x5229;&#x7528;&#x8FD9;&#x4E2A;&#x7A7A;&#x7740;&#x7684;&#x683C;&#x5B50;&#x79FB;&#x52A8;&#x5176;&#x4ED6;&#x6570;&#x5B57;&#x3002;&#x4F60;&#x9700;&#x8981;&#x901A;&#x8FC7;&#x79FB;&#x52A8;&#x8FD9;&#x4E9B;&#x6570;&#x5B57;&#xFF0C;&#x5F97;&#x5230;&#x67D0;&#x4E2A;&#x7279;&#x5B9A;&#x6392;&#x5217;&#x987A;&#x5E8F;&#xFF0C;&#x8FD9;&#x6837;&#x5C31;&#x7B97;&#x8D62;&#x4E86;&#x3002;</p>
<p>&#x6211;&#x5C0F;&#x65F6;&#x5019;&#x8FD8;&#x73A9;&#x8FC7;&#x4E00;&#x6B3E;&#x53EB;&#x505A;&#x300C;&#x534E;&#x5BB9;&#x9053;&#x300D;&#x7684;&#x76CA;&#x667A;&#x6E38;&#x620F;&#xFF0C;&#x4E5F;&#x548C;&#x6ED1;&#x52A8;&#x62FC;&#x56FE;&#x6BD4;&#x8F83;&#x7C7B;&#x4F3C;</p>
<p>&#x90A3;&#x4E48;&#x8FD9;&#x79CD;&#x6E38;&#x620F;&#x600E;&#x4E48;&#x73A9;&#x5462;&#xFF1F;&#x6211;&#x8BB0;&#x5F97;&#x662F;&#x6709;&#x4E00;&#x4E9B;&#x5957;&#x8DEF;&#x7684;&#xFF0C;&#x7C7B;&#x4F3C;&#x4E8E;&#x9B54;&#x65B9;&#x8FD8;&#x539F;&#x516C;&#x5F0F;&#x3002;&#x4F46;&#x662F;&#x6211;&#x4EEC;&#x4ECA;&#x5929;&#x4E0D;&#x6765;&#x7814;&#x7A76;&#x8BA9;&#x4EBA;&#x5934;&#x79C3;&#x7684;&#x6280;&#x5DE7;&#xFF0C;<strong>&#x8FD9;&#x4E9B;&#x76CA;&#x667A;&#x6E38;&#x620F;&#x901A;&#x901A;&#x53EF;&#x4EE5;&#x7528;&#x66B4;&#x529B;&#x641C;&#x7D22;&#x7B97;&#x6CD5;&#x89E3;&#x51B3;&#xFF0C;&#x6240;&#x4EE5;&#x4ECA;&#x5929;&#x6211;&#x4EEC;&#x5C31;&#x5B66;&#x4EE5;&#x81F4;&#x7528;&#xFF0C;&#x7528; BFS &#x7B97;&#x6CD5;&#x6846;&#x67B6;&#x6765;&#x79D2;&#x6740;&#x8FD9;&#x4E9B;&#x6E38;&#x620F;</strong>&#x3002;</p>
<h3 id="&#x4E00;&#x3001;&#x9898;&#x76EE;&#x89E3;&#x6790;"><a name="&#x4E00;&#x3001;&#x9898;&#x76EE;&#x89E3;&#x6790;" class="anchor-navigation-ex-anchor" href="#&#x4E00;&#x3001;&#x9898;&#x76EE;&#x89E3;&#x6790;"><i class="fa fa-link" aria-hidden="true"></i></a><a name="&#x4E00;&#x3001;&#x9898;&#x76EE;&#x89E3;&#x6790;" class="plugin-anchor" href="#&#x4E00;&#x3001;&#x9898;&#x76EE;&#x89E3;&#x6790;"><i class="fa fa-link" aria-hidden="true"></i></a>&#x4E00;&#x3001;&#x9898;&#x76EE;&#x89E3;&#x6790;</h3>
<p>LeetCode &#x7B2C; 773 &#x9898;&#x5C31;&#x662F;&#x6ED1;&#x52A8;&#x62FC;&#x56FE;&#x95EE;&#x9898;&#xFF0C;&#x9898;&#x76EE;&#x7684;&#x610F;&#x601D;&#x5982;&#x4E0B;&#xFF1A;</p>
<p>&#x7ED9;&#x4F60;&#x4E00;&#x4E2A; 2x3 &#x7684;&#x6ED1;&#x52A8;&#x62FC;&#x56FE;&#xFF0C;&#x7528;&#x4E00;&#x4E2A; 2x3 &#x7684;&#x6570;&#x7EC4;<code>board</code>&#x8868;&#x793A;&#x3002;&#x62FC;&#x56FE;&#x4E2D;&#x6709;&#x6570;&#x5B57; 0~5 &#x516D;&#x4E2A;&#x6570;&#xFF0C;&#x5176;&#x4E2D;&#x6570;&#x5B57; 0 &#x5C31;&#x8868;&#x793A;&#x90A3;&#x4E2A;&#x7A7A;&#x7740;&#x7684;&#x683C;&#x5B50;&#xFF0C;&#x4F60;&#x53EF;&#x4EE5;&#x79FB;&#x52A8;&#x5176;&#x4E2D;&#x7684;&#x6570;&#x5B57;&#xFF0C;&#x5F53;<code>board</code>&#x53D8;&#x4E3A;<code>[[1,2,3],[4,5,0]]</code>&#x65F6;&#xFF0C;&#x8D62;&#x5F97;&#x6E38;&#x620F;&#x3002;</p>
<p>&#x8BF7;&#x4F60;&#x5199;&#x4E00;&#x4E2A;&#x7B97;&#x6CD5;&#xFF0C;&#x8BA1;&#x7B97;&#x8D62;&#x5F97;&#x6E38;&#x620F;&#x9700;&#x8981;&#x7684;&#x6700;&#x5C11;&#x79FB;&#x52A8;&#x6B21;&#x6570;&#xFF0C;&#x5982;&#x679C;&#x4E0D;&#x80FD;&#x8D62;&#x5F97;&#x6E38;&#x620F;&#xFF0C;&#x8FD4;&#x56DE; -1&#x3002;</p>
<p>&#x6BD4;&#x5982;&#x8BF4;&#x8F93;&#x5165;&#x7684;&#x4E8C;&#x7EF4;&#x6570;&#x7EC4;<code>board = [[4,1,2],[5,0,3]]</code>&#xFF0C;&#x7B97;&#x6CD5;&#x5E94;&#x8BE5;&#x8FD4;&#x56DE; 5&#xFF1A;</p>
<p><img src="https://gitee.com/zisuu/picture/raw/master/img/20201227152539.png" alt="image-20201227152539442"></p>
<p>&#x5982;&#x679C;&#x8F93;&#x5165;&#x7684;&#x662F;<code>board = [[1,2,3],[4,0,5]]</code>&#xFF0C;&#x5219;&#x7B97;&#x6CD5;&#x8FD4;&#x56DE; -1&#xFF0C;&#x56E0;&#x4E3A;&#x8FD9;&#x79CD;&#x5C40;&#x9762;&#x4E0B;&#x65E0;&#x8BBA;&#x5982;&#x4F55;&#x90FD;&#x4E0D;&#x80FD;&#x8D62;&#x5F97;&#x6E38;&#x620F;&#x3002;</p>
<h3 id="&#x4E8C;&#x3001;&#x601D;&#x8DEF;&#x5206;&#x6790;"><a name="&#x4E8C;&#x3001;&#x601D;&#x8DEF;&#x5206;&#x6790;" class="anchor-navigation-ex-anchor" href="#&#x4E8C;&#x3001;&#x601D;&#x8DEF;&#x5206;&#x6790;"><i class="fa fa-link" aria-hidden="true"></i></a><a name="&#x4E8C;&#x3001;&#x601D;&#x8DEF;&#x5206;&#x6790;" class="plugin-anchor" href="#&#x4E8C;&#x3001;&#x601D;&#x8DEF;&#x5206;&#x6790;"><i class="fa fa-link" aria-hidden="true"></i></a>&#x4E8C;&#x3001;&#x601D;&#x8DEF;&#x5206;&#x6790;</h3>
<p>&#x5BF9;&#x4E8E;&#x8FD9;&#x79CD;&#x8BA1;&#x7B97;&#x6700;&#x5C0F;&#x6B65;&#x6570;&#x7684;&#x95EE;&#x9898;&#xFF0C;&#x6211;&#x4EEC;&#x5C31;&#x8981;&#x654F;&#x611F;&#x5730;&#x60F3;&#x5230; BFS &#x7B97;&#x6CD5;&#x3002;</p>
<p>&#x8FD9;&#x4E2A;&#x9898;&#x76EE;&#x8F6C;&#x5316;&#x6210; BFS &#x95EE;&#x9898;&#x662F;&#x6709;&#x4E00;&#x4E9B;&#x6280;&#x5DE7;&#x7684;&#xFF0C;&#x6211;&#x4EEC;&#x9762;&#x4E34;&#x5982;&#x4E0B;&#x95EE;&#x9898;&#xFF1A;</p>
<p>1&#x3001;&#x4E00;&#x822C;&#x7684; BFS &#x7B97;&#x6CD5;&#xFF0C;&#x662F;&#x4ECE;&#x4E00;&#x4E2A;&#x8D77;&#x70B9;<code>start</code>&#x5F00;&#x59CB;&#xFF0C;&#x5411;&#x7EC8;&#x70B9;<code>target</code>&#x8FDB;&#x884C;&#x5BFB;&#x8DEF;&#xFF0C;&#x4F46;&#x662F;&#x62FC;&#x56FE;&#x95EE;&#x9898;&#x4E0D;&#x662F;&#x5728;&#x5BFB;&#x8DEF;&#xFF0C;&#x800C;&#x662F;&#x5728;&#x4E0D;&#x65AD;&#x4EA4;&#x6362;&#x6570;&#x5B57;&#xFF0C;&#x8FD9;&#x5E94;&#x8BE5;&#x600E;&#x4E48;&#x8F6C;&#x5316;&#x6210; BFS &#x7B97;&#x6CD5;&#x95EE;&#x9898;&#x5462;&#xFF1F;</p>
<p>2&#x3001;&#x5373;&#x4FBF;&#x8FD9;&#x4E2A;&#x95EE;&#x9898;&#x80FD;&#x591F;&#x8F6C;&#x5316;&#x6210; BFS &#x95EE;&#x9898;&#xFF0C;&#x5982;&#x4F55;&#x5904;&#x7406;&#x8D77;&#x70B9;<code>start</code>&#x548C;&#x7EC8;&#x70B9;<code>target</code>&#xFF1F;&#x5B83;&#x4EEC;&#x90FD;&#x662F;&#x6570;&#x7EC4;&#x54CE;&#xFF0C;&#x628A;&#x6570;&#x7EC4;&#x653E;&#x8FDB;&#x961F;&#x5217;&#xFF0C;&#x5957; BFS &#x6846;&#x67B6;&#xFF0C;&#x60F3;&#x60F3;&#x5C31;&#x6BD4;&#x8F83;&#x9EBB;&#x70E6;&#x4E14;&#x4F4E;&#x6548;&#x3002;</p>
<p>&#x9996;&#x5148;&#x56DE;&#x7B54;&#x7B2C;&#x4E00;&#x4E2A;&#x95EE;&#x9898;&#xFF0C;<strong>BFS &#x7B97;&#x6CD5;&#x5E76;&#x4E0D;&#x53EA;&#x662F;&#x4E00;&#x4E2A;&#x5BFB;&#x8DEF;&#x7B97;&#x6CD5;&#xFF0C;&#x800C;&#x662F;&#x4E00;&#x79CD;&#x66B4;&#x529B;&#x641C;&#x7D22;&#x7B97;&#x6CD5;</strong>&#xFF0C;&#x53EA;&#x8981;&#x6D89;&#x53CA;&#x66B4;&#x529B;&#x7A77;&#x4E3E;&#x7684;&#x95EE;&#x9898;&#xFF0C;BFS &#x5C31;&#x53EF;&#x4EE5;&#x7528;&#xFF0C;&#x800C;&#x4E14;&#x53EF;&#x4EE5;&#x6700;&#x5FEB;&#x5730;&#x627E;&#x5230;&#x7B54;&#x6848;&#x3002;</p>
<p>&#x4F60;&#x60F3;&#x60F3;&#x8BA1;&#x7B97;&#x673A;&#x600E;&#x4E48;&#x89E3;&#x51B3;&#x95EE;&#x9898;&#x7684;&#xFF1F;&#x54EA;&#x6709;&#x90A3;&#x4E48;&#x591A;&#x5947;&#x6280;&#x6DEB;&#x5DE7;&#xFF0C;&#x672C;&#x8D28;&#x4E0A;&#x5C31;&#x662F;&#x628A;&#x6240;&#x6709;&#x53EF;&#x884C;&#x89E3;&#x66B4;&#x529B;&#x7A77;&#x4E3E;&#x51FA;&#x6765;&#xFF0C;&#x7136;&#x540E;&#x4ECE;&#x4E2D;&#x627E;&#x5230;&#x4E00;&#x4E2A;&#x6700;&#x4F18;&#x89E3;&#x7F62;&#x4E86;&#x3002;</p>
<p>&#x660E;&#x767D;&#x4E86;&#x8FD9;&#x4E2A;&#x9053;&#x7406;&#xFF0C;&#x6211;&#x4EEC;&#x7684;&#x95EE;&#x9898;&#x5C31;&#x8F6C;&#x5316;&#x6210;&#x4E86;&#xFF1A;<strong>&#x5982;&#x4F55;&#x7A77;&#x4E3E;&#x51FA;<code>board</code>&#x5F53;&#x524D;&#x5C40;&#x9762;&#x4E0B;&#x53EF;&#x80FD;&#x884D;&#x751F;&#x51FA;&#x7684;&#x6240;&#x6709;&#x5C40;&#x9762;</strong>&#xFF1F;&#x8FD9;&#x5C31;&#x7B80;&#x5355;&#x4E86;&#xFF0C;&#x770B;&#x6570;&#x5B57; 0 &#x7684;&#x4F4D;&#x7F6E;&#x5457;&#xFF0C;&#x548C;&#x4E0A;&#x4E0B;&#x5DE6;&#x53F3;&#x7684;&#x6570;&#x5B57;&#x8FDB;&#x884C;&#x4EA4;&#x6362;&#x5C31;&#x884C;&#x4E86;&#xFF1A;</p>
<p><img src="https://gitee.com/zisuu/picture/raw/master/img/20201227152544.png" alt="image-20201227152544875"></p>
<p>&#x8FD9;&#x6837;&#x5176;&#x5B9E;&#x5C31;&#x662F;&#x4E00;&#x4E2A; BFS &#x95EE;&#x9898;&#xFF0C;&#x6BCF;&#x6B21;&#x5148;&#x627E;&#x5230;&#x6570;&#x5B57; 0&#xFF0C;&#x7136;&#x540E;&#x548C;&#x5468;&#x56F4;&#x7684;&#x6570;&#x5B57;&#x8FDB;&#x884C;&#x4EA4;&#x6362;&#xFF0C;&#x5F62;&#x6210;&#x65B0;&#x7684;&#x5C40;&#x9762;&#x52A0;&#x5165;&#x961F;&#x5217;&#x2026;&#x2026; &#x5F53;&#x7B2C;&#x4E00;&#x6B21;&#x5230;&#x8FBE;<code>target</code>&#x65F6;&#xFF0C;&#x5C31;&#x5F97;&#x5230;&#x4E86;&#x8D62;&#x5F97;&#x6E38;&#x620F;&#x7684;&#x6700;&#x5C11;&#x6B65;&#x6570;&#x3002;</p>
<p>&#x5BF9;&#x4E8E;&#x7B2C;&#x4E8C;&#x4E2A;&#x95EE;&#x9898;&#xFF0C;&#x6211;&#x4EEC;&#x8FD9;&#x91CC;&#x7684;<code>board</code>&#x4EC5;&#x4EC5;&#x662F; 2x3 &#x7684;&#x4E8C;&#x7EF4;&#x6570;&#x7EC4;&#xFF0C;&#x6240;&#x4EE5;&#x53EF;&#x4EE5;&#x538B;&#x7F29;&#x6210;&#x4E00;&#x4E2A;&#x4E00;&#x7EF4;&#x5B57;&#x7B26;&#x4E32;&#x3002;<strong>&#x5176;&#x4E2D;&#x6BD4;&#x8F83;&#x6709;&#x6280;&#x5DE7;&#x6027;&#x7684;&#x70B9;&#x5728;&#x4E8E;&#xFF0C;&#x4E8C;&#x7EF4;&#x6570;&#x7EC4;&#x6709;&#x300C;&#x4E0A;&#x4E0B;&#x5DE6;&#x53F3;&#x300D;&#x7684;&#x6982;&#x5FF5;&#xFF0C;&#x538B;&#x7F29;&#x6210;&#x4E00;&#x7EF4;&#x540E;&#xFF0C;&#x5982;&#x4F55;&#x5F97;&#x5230;&#x67D0;&#x4E00;&#x4E2A;&#x7D22;&#x5F15;&#x4E0A;&#x4E0B;&#x5DE6;&#x53F3;&#x7684;&#x7D22;&#x5F15;</strong>&#xFF1F;</p>
<p>&#x5F88;&#x7B80;&#x5355;&#xFF0C;&#x6211;&#x4EEC;&#x53EA;&#x8981;&#x624B;&#x52A8;&#x5199;&#x51FA;&#x6765;&#x8FD9;&#x4E2A;&#x6620;&#x5C04;&#x5C31;&#x884C;&#x4E86;&#xFF1A;</p>
<pre><code>vector&lt;vector&lt;int&gt;&gt; neighbor = {
    { 1, 3 },
    { 0, 4, 2 },
    { 1, 5 },
    { 0, 4 },
    { 3, 1, 5 },
    { 4, 2 }
};
</code></pre><p><strong>&#x8FD9;&#x4E2A;&#x542B;&#x4E49;&#x5C31;&#x662F;&#xFF0C;&#x5728;&#x4E00;&#x7EF4;&#x5B57;&#x7B26;&#x4E32;&#x4E2D;&#xFF0C;&#x7D22;&#x5F15;<code>i</code>&#x5728;&#x4E8C;&#x7EF4;&#x6570;&#x7EC4;&#x4E2D;&#x7684;&#x7684;&#x76F8;&#x90BB;&#x7D22;&#x5F15;&#x4E3A;<code>neighbor[i]</code></strong>&#xFF0C;&#xFF1A;</p>
<p><img src="https://gitee.com/zisuu/picture/raw/master/img/20201227152550.png" alt="image-20201227152550862"></p>
<p>&#x81F3;&#x6B64;&#xFF0C;&#x6211;&#x4EEC;&#x5C31;&#x628A;&#x8FD9;&#x4E2A;&#x95EE;&#x9898;&#x5B8C;&#x5168;&#x8F6C;&#x5316;&#x6210;&#x6807;&#x51C6;&#x7684; BFS &#x95EE;&#x9898;&#x4E86;&#xFF0C;&#x501F;&#x52A9;&#x524D;&#x6587; <a href="http://mp.weixin.qq.com/s?__biz=MzAxODQxMDM0Mw==&amp;mid=2247485134&amp;idx=1&amp;sn=fd345f8a93dc4444bcc65c57bb46fc35&amp;chksm=9bd7f8c6aca071d04c4d383f96f2b567ad44dc3e67d1c3926ec92d6a3bcc3273de138b36a0d9&amp;scene=21#wechat_redirect" target="_blank">BFS &#x7B97;&#x6CD5;&#x6846;&#x67B6;&#x5957;&#x8DEF;&#x8BE6;&#x89E3;</a> &#x7684;&#x4EE3;&#x7801;&#x6846;&#x67B6;&#xFF0C;&#x76F4;&#x63A5;&#x5C31;&#x53EF;&#x4EE5;&#x5957;&#x51FA;&#x89E3;&#x6CD5;&#x4EE3;&#x7801;&#x4E86;&#xFF1A;</p>
<pre><code>int slidingPuzzle(vector&lt;vector&lt;int&gt;&gt;&amp; board) {
    int m = 2, n = 3;
    string start = &quot;&quot;;
    string target = &quot;123450&quot;;
    // &#x5C06; 2x3 &#x7684;&#x6570;&#x7EC4;&#x8F6C;&#x5316;&#x6210;&#x5B57;&#x7B26;&#x4E32;
    for (int i = 0; i &lt; m; i++) {
        for (int j = 0; j &lt; n; j++) {
            start.push_back(board[i][j] + &apos;0&apos;);
        }
    }
    // &#x8BB0;&#x5F55;&#x4E00;&#x7EF4;&#x5B57;&#x7B26;&#x4E32;&#x7684;&#x76F8;&#x90BB;&#x7D22;&#x5F15;
    vector&lt;vector&lt;int&gt;&gt; neighbor = {
        { 1, 3 },
        { 0, 4, 2 },
        { 1, 5 },
        { 0, 4 },
        { 3, 1, 5 },
        { 4, 2 }
    };

    /******* BFS &#x7B97;&#x6CD5;&#x6846;&#x67B6;&#x5F00;&#x59CB; *******/
    queue&lt;string&gt; q;
    unordered_set&lt;string&gt; visited;
    q.push(start);
    visited.insert(start);

    int step = 0;
    while (!q.empty()) {
        int sz = q.size();
        for (int i = 0; i &lt; sz; i++) {
            string cur = q.front(); q.pop();
            // &#x5224;&#x65AD;&#x662F;&#x5426;&#x8FBE;&#x5230;&#x76EE;&#x6807;&#x5C40;&#x9762;
            if (target == cur) {
                return step;
            }
            // &#x627E;&#x5230;&#x6570;&#x5B57; 0 &#x7684;&#x7D22;&#x5F15;
            int idx = 0;
            for (; cur[idx] != &apos;0&apos;; idx++);
            // &#x5C06;&#x6570;&#x5B57; 0 &#x548C;&#x76F8;&#x90BB;&#x7684;&#x6570;&#x5B57;&#x4EA4;&#x6362;&#x4F4D;&#x7F6E;
            for (int adj : neighbor[idx]) {
                string new_board = cur;
                swap(new_board[adj], new_board[idx]);
                // &#x9632;&#x6B62;&#x8D70;&#x56DE;&#x5934;&#x8DEF;
                if (!visited.count(new_board)) {
                    q.push(new_board);
                    visited.insert(new_board);
                }
            }
        }
        step++;
    }
    return -1;
    /******* BFS &#x7B97;&#x6CD5;&#x6846;&#x67B6;&#x7ED3;&#x675F; *******/
}
</code></pre><p>&#x81F3;&#x6B64;&#xFF0C;&#x8FD9;&#x9053;&#x9898;&#x76EE;&#x5C31;&#x89E3;&#x51B3;&#x4E86;&#xFF0C;&#x5176;&#x5B9E;&#x6846;&#x67B6;&#x5B8C;&#x5168;&#x6CA1;&#x6709;&#x53D8;&#xFF0C;&#x5957;&#x8DEF;&#x90FD;&#x662F;&#x4E00;&#x6837;&#x7684;&#xFF0C;&#x6211;&#x4EEC;&#x53EA;&#x662F;&#x82B1;&#x4E86;&#x6BD4;&#x8F83;&#x591A;&#x7684;&#x65F6;&#x95F4;&#x5C06;&#x6ED1;&#x52A8;&#x62FC;&#x56FE;&#x6E38;&#x620F;&#x8F6C;&#x5316;&#x6210; BFS &#x7B97;&#x6CD5;&#x3002;</p>
<p><strong>&#x5F88;&#x591A;&#x76CA;&#x667A;&#x6E38;&#x620F;&#x90FD;&#x662F;&#x8FD9;&#x6837;&#xFF0C;&#x867D;&#x7136;&#x770B;&#x8D77;&#x6765;&#x7279;&#x522B;&#x5DE7;&#x5999;&#xFF0C;&#x4F46;&#x90FD;&#x67B6;&#x4E0D;&#x4F4F;&#x66B4;&#x529B;&#x7A77;&#x4E3E;</strong>&#xFF0C;&#x5E38;&#x7528;&#x7684;&#x7B97;&#x6CD5;&#x5C31;&#x662F;&#x56DE;&#x6EAF;&#x7B97;&#x6CD5;&#x6216;&#x8005; BFS &#x7B97;&#x6CD5;&#xFF0C;&#x611F;&#x5174;&#x8DA3;&#x7684;&#x8BDD;&#x6211;&#x4EEC;&#x4EE5;&#x540E;&#x518D;&#x804A;&#x3002;</p>

<script>console.log("plugin-popup....");document.onclick = function(e){ e.target.tagName === "IMG" && window.open(e.target.src,e.target.src)}</script><style>img{cursor:pointer}</style>
                                
                                </section>
                            
    </div>
    <div class="search-results">
        <div class="has-results">
            
            <h1 class="search-results-title"><span class='search-results-count'></span> results matching "<span class='search-query'></span>"</h1>
            <ul class="search-results-list"></ul>
            
        </div>
        <div class="no-results">
            
            <h1 class="search-results-title">No results matching "<span class='search-query'></span>"</h1>
            
        </div>
    </div>
</div>

                        </div>
                    </div>
                
            </div>

            
                
                <a href="2.深度优先搜索题目集.html" class="navigation navigation-prev " aria-label="Previous page: 2.深搜题目集">
                    <i class="fa fa-angle-left"></i>
                </a>
                
                
                <a href="../jvm/1.jvm内存结构.html" class="navigation navigation-next " aria-label="Next page: 1.jvm内存结构">
                    <i class="fa fa-angle-right"></i>
                </a>
                
            
        
    </div>

    <script>
        var gitbook = gitbook || [];
        gitbook.push(function() {
            gitbook.page.hasChanged({"page":{"title":"3.广度优先搜索算法","level":"4.5","depth":1,"next":{"title":"1.jvm内存结构","level":"5.1","depth":1,"path":"jvm/1.jvm内存结构.md","ref":"jvm/1.jvm内存结构.md","articles":[]},"previous":{"title":"2.深搜题目集","level":"4.4","depth":1,"path":"算法/2.深度优先搜索题目集.md","ref":"算法/2.深度优先搜索题目集.md","articles":[]},"dir":"ltr"},"config":{"plugins":["-sharing","splitter","expandable-chapters-small","anchors","sharing-plus","anchor-navigation-ex","favicon","expandable-chapters","toggle-chapters","back-to-top-button","code","-lunr","-search","search-pro","pageview-count","popup","livereload"],"styles":{"website":"./styles/website.css"},"pluginsConfig":{"livereload":{},"splitter":{},"search-pro":{},"sharing-plus":{"qq":false,"all":["facebook","google","twitter","instapaper","linkedin","pocket","stumbleupon"],"douban":false,"facebook":true,"weibo":false,"instapaper":false,"whatsapp":false,"hatenaBookmark":false,"twitter":true,"messenger":false,"line":false,"vk":false,"pocket":true,"google":false,"viber":false,"stumbleupon":false,"qzone":false,"linkedin":false},"popup":{},"code":{"copyButtons":true},"fontsettings":{"theme":"white","family":"sans","size":2},"highlight":{},"anchor-navigation-ex":{"associatedWithSummary":true,"float":{"floatIcon":"fa fa-navicon","level1Icon":"","level2Icon":"","level3Icon":"","showLevelIcon":false},"mode":"float","multipleH1":true,"pageTop":{"level1Icon":"","level2Icon":"","level3Icon":"","showLevelIcon":false},"printLog":false,"showGoTop":true,"showLevel":false},"favicon":{},"back-to-top-button":{},"pageview-count":{},"expandable-chapters-small":{},"sharing":{"qq":false,"all":["google","facebook","weibo","twitter","qq","qzone","linkedin","pocket"],"douban":false,"facebook":false,"weibo":false,"instapaper":false,"whatsapp":false,"hatenaBookmark":false,"twitter":false,"messenger":false,"line":false,"vk":false,"pocket":false,"google":false,"viber":false,"stumbleupon":false,"qzone":false,"linkedin":false},"theme-default":{"styles":{"website":"styles/website.css","pdf":"styles/pdf.css","epub":"styles/epub.css","mobi":"styles/mobi.css","ebook":"styles/ebook.css","print":"styles/print.css"},"showLevel":false},"anchors":{},"toggle-chapters":{},"expandable-chapters":{}},"theme":"default","author":"hzh","pdf":{"pageNumbers":true,"fontSize":12,"fontFamily":"Arial","paperSize":"a4","chapterMark":"pagebreak","pageBreaksBefore":"/","margin":{"right":62,"left":62,"top":56,"bottom":56}},"structure":{"langs":"LANGS.md","readme":"README.md","glossary":"GLOSSARY.md","summary":"SUMMARY.md"},"variables":{},"title":"计算机 ,java , 大数据 基础知识体系","language":"zh-hans","gitbook":"3.2.3"},"file":{"path":"算法/3.广度优先搜索.md","mtime":"2020-12-27T07:25:54.802Z","type":"markdown"},"gitbook":{"version":"3.2.3","time":"2020-12-30T11:12:56.611Z"},"basePath":"..","book":{"language":""}});
        });
    </script>
</div>

        
    <script src="../gitbook/gitbook.js"></script>
    <script src="../gitbook/theme.js"></script>
    
        
        <script src="../gitbook/gitbook-plugin-splitter/splitter.js"></script>
        
    
        
        <script src="../gitbook/gitbook-plugin-expandable-chapters-small/expandable-chapters-small.js"></script>
        
    
        
        <script src="../gitbook/gitbook-plugin-sharing-plus/buttons.js"></script>
        
    
        
        <script src="../gitbook/gitbook-plugin-expandable-chapters/expandable-chapters.js"></script>
        
    
        
        <script src="../gitbook/gitbook-plugin-toggle-chapters/toggle.js"></script>
        
    
        
        <script src="../gitbook/gitbook-plugin-back-to-top-button/plugin.js"></script>
        
    
        
        <script src="../gitbook/gitbook-plugin-code/plugin.js"></script>
        
    
        
        <script src="../gitbook/gitbook-plugin-search-pro/jquery.mark.min.js"></script>
        
    
        
        <script src="../gitbook/gitbook-plugin-search-pro/search.js"></script>
        
    
        
        <script src="../gitbook/gitbook-plugin-pageview-count/plugin.js"></script>
        
    
        
        <script src="../gitbook/gitbook-plugin-livereload/plugin.js"></script>
        
    
        
        <script src="../gitbook/gitbook-plugin-fontsettings/fontsettings.js"></script>
        
    

    </body>
</html>

